Definitely use either Nitrile or Viton O'rings, any good bearing shop will also sell o'rings. I also use Krytox lube which is Nitrox safe, it's a bit expensive and sometimes hard to get but a tube lasts ages.
Generally, manufaturers specify that you should always replace the 'dynamic orings' (ones that are sliding/rotating or moving) and replace the 'static' orings (ones that are compressed between two parts) on condition, but as Camerone mentioned o'rings are extremely cheap in the scheme of things so just replace any you disturb.
Common sizes you'll need are: (assuming this is internationally standardised)
003 - Used on the High pressure swivel at the guage end
010 - Used on second stage end of the hoses and in the inflator hose connector and inside some regs. Common on most knife edge seats in second stages.
011 - Used on the First stage end of the hoses and the port plugs except the HP hose.
012 - Used on the HP hose at the first stage and HP port plugs
014 - Moderately common tank valve oring
114 - Very common tank valve oring in Oz
013, 016, 022, are also pretty common but can be reg dependant.
214 is the one at the base of the tank valve in the tank. You should always get this one done when your tank is in for test.
It may also be worth checking into servicing kits for your particular brand of reg. You should replace your High Pressure and low pressure seats pretty regularly, along with diaphragms and a few other bits n pieces. More often than not these days the manufacturers produce these kits with all the bits they want replaced on the annual service and charge a premium for seperated parts so you pay more for the individual bits than you would of for the kit. You will more than likely still require the hose oring sizes though.
It's worth buying the specialist tools you require for a particular reg as well, I've seen several first and second stages scrapped from incorrect tools.
If you need a what too look for list let me know and I'll write some guidelines out for you but it might be easier if I knew what you owned.
To prep for nitrox you need to make sure you get rid of all the silicone grease from every little nook and cranny. You will need some kind of strong industrial detergent that is safe for humans, best to go with something along the lines of what they use in the food preperation industries...aslong as it's not part bleach...
If your going to be doing this regularly it will be well worth you investing in an ultra sonic cleaner, just don't stick your fingers in it while it's running....
Good Luck
Woz