What kind of format should I use? Read here that ogg/vorbis is a good one, if feasible.
In terms of audio quality, at higher bitrates there's not much difference between MP3, AAC, or OGG. i.e. At higher bitrates, any of them will sound identical to the uncompressed original with most program material.
So, it really comes down to which format is easiest to decode, or which format you normally use or prefer. There's an MP3 shield for the Arduino, so that might be the way to go.
Ogg is open source, whereas the manufacturer of an MP3 or AAC decoder chip has to pay a royalty that gets passed on to you. If you can write (or port) the decoder firmware yourself, and figure-out what processor to run it on, you can "get around" the royalties for home/personal use.
If you can go up to around 800kbps, you can use FLAC (lossless open source compression). But, I have no idea what's involved in building a hardware FLAC decoder.