You can get an IRman for your PC, see
[Link: evation.com]nice unit, good sensitivity, lot's of software, including plug in's for mp3 players.
You can use the OmniRemote to talk to it using any of your programed remote codes, just bind those codes to the functions you want performed on the PC side.
The hard part is doing the Palm DB -> IR output part. Since there is no library to perform this function yet it makes it non-trivial. The best I can think of is to associate a unique number with each album/track. Then on the Palm lookup the number via a nice browser, switch to OmniRemote/Mp3 and enter the number. On the PC side you would have to have some smarts that matches the number back to the album/track ... Of course this is a real no-no in terms of human factors as it requires use of short term memory!
I actually did something similar to this but used the serial port connection with the VT100 emulator, sending shell commands to control the mp3 player on my Linux box!
A more exotic interface could be built using RF and/or using the wireless connection to a web server ... There is a rs-232<->RF<->rs-232 link that has 25 mile range! Requires a license though, and of course one would need a small nuclear power plant for the amp/speakers.