I believe they all do. The only exception, if I recall correctly, is that the very first iPods (the regular iPods) don't support AAC (but do support MP3 at 256 kbps). Otherwise, all iPods support AAC and MP3 256 kbps audio.
A majority of my songs are MP3 @ 256kb/s. I have a few iTunes Store-bought songs (which I am assuming are AAC 256kb/s). Will these be at 256kb/s on the 3rd Gen. iPod Classic or 1st/2nd Gen iPod Mini I can safely assume then?