Kryptonians absolutely need oxygen. When Superman exerts himself in battle (or when lifting a battleship or what have you), he is often seen breathing heavily afterwards - he obviously needs the greater oxygen intake. It's possible, of course, that he actually requires one of the other common gasses in the atmosphere, but I'm fairly certain it's good old oxygen he breathes.
Superman can hold his breath for a long time, and his invulnerable physiology makes it safe for him to do so in a vacuum. Generally, this means he can absolutely travel for a short distance in space without problem.
In the 90s animated series he's shown in some form of space suit when he travels in space for long periods (or in a spaceship, which of course provides air). Outside of that, or when this isn't possible, he's typically seen with another character (such as a Green Lantern) that can provide atmosphere.
In the silver age comics (notably the 60s) Superman was seen to fly through the vacuum of space without trouble, frequently talking to his cousin (SuperGirl) through super-hypnotism.
In short, this has changed (frequently) through the ages and mediums. With the New52 reboot, we will have to wait and see.