This is how I'm planning on doing mine, as well... eventually (been planning it for over a year now). Anyway, some things I've found that might help out. Sorry if they're obvious, but it might save someone some time.
For a simple web frontend for playlist control, check out glirnath:
I've tested it in our media center, and it works pretty well. It would take a bit of PHP knowledge to customize anything outside the logo/color scheme. Alternatively, check out mpd:
It's a daemon that handles the playback. Control is done through a number of frontends, and they have a lot, from command-line, X and a few different web ones. The nice thing about this is (they say) it can remember it's position between shutdowns, so it would make continuation after reboots easy.
PDA's with 802.11 built in are common now, so it's just a matter of what features you want (keypad, etc). Unless you can do Ad-Hoc, which I've never had much luck getting working reliably, you'll want to get the linux machine to act as an access point, so you don't have a separate AP in your car. If you're familiar with OpenBSD, this would be much much easier, but it can be done on Linux as well:
Depending on the PDA you get, you can probably get an ssh client, but I don't consider it that important. Once set up, you shouldn't have to do much. The only task I see needing to be performed is getting new music into the collection. I'd just set up a Samba share for the mp3 directory, and a share for a USB thumb drive, and you can copy new music over easily from the PDA. Or set up a webpage that you can call to copy stuff from the thumb drive to the music directory. Most common functions could be handled this way. Anything else would require a shell, and if you have a laptop, you can bring that into the car with you, get on the network, and ssh in. I don't need X; if you do, well, it gets more complicated I guess ;-)
That's all I can think of for now.