Well, with some insight from Lincoln Stein, author of the Apache::MP3 Perl module, I've successfully implemented seeking in my MP3 engine. Turns out that out of XMMS and WinAMP, only WinAMP supports seeking in HTTP/1.1 streams so far, but XMMS will follow I'm sure. So you can now jump to different parts of a song, even when it's streamed!
The trick is that when you move the seekbar in WinAMP to seek in a song, WinAMP sends an HTTP/1.1 header that looks like:
Range: bytes=192345-
to the server, which I can then parse, use the byte offset to do a seek on the file handle, and then send that back to the client.
w00t! as some might say. :)