Are you ripping cds or buying online? If you have cds, if at all possible you should rip into a lossless format like FLAC, and from there transcode into a lossy format like AAC or mp3 for your player. This way you still have a pure original if you get a new player that uses a different format. Transcoding from one lossy format to another doesn't really work all that well.
I'd avoid WMA, it's Microsoft's half-hearted attempt to get music into their standard. mp3 is the most common format, almost everything plays it. AAC is basically an upgraded mp3, and on paper is better, but I haven't done any ear-to-ear comparisons. As long as your player supports it, might as well try AAC, it's becoming more and more common.