Mindboards

Would something like this be suitable? http://www.nxtprograms.com/NXT2/explorer/index.html

Sure, but those wheels aren't ideal (should be a lot better than tracks though).

Do you have an example of what is best to use?

I just thought, with all this talk of formulas and best tyres and so on might be irrelevant.
Can't I just use a compass sensor on the robot to find out very accurately when 90 degrees has been turned?

The wheels that are included with the NXT 1.0 set, or the big wheels included with the RCX are good. Basically you want as little rubber as possible to touch the ground.

The wheels included with the NXT 2.0 set are also fine, they are just fairly wide where they touch the ground.

For more accurate turns, the further apart the wheels, the better (and also the slower it will turn).

Oh, if you have a compass, yes, that would be good. A compass is based on an absolute (the magnetic field of the earth), so the values won't drift with inaccuracies. However, a compass' readings are very negatively affected by it's surroundings, so the immediate accuracy could be off significantly.

Ideally you would use both the compass and the encoders, and combine the values using a filter. It would be very complicated, and certainly not something I would recommend for a beginner (or even someone that is intermediate).

If if the initial values we off though I guess it would be good enough to tell if i move by a certain amount of degrees
For instance if it said I was at 10 degrees and then i move by 90 degrees than it will read 100 i will have still moved by the correct amount of 90 degrees

I want to suggest a different perspective. Forget about wheels and compasses for the moment.

The amount of turn is a function of wheel diameter, wheel distance and radius (distance between robot center and origin of turning cycle). Diameter and wheel distance are constants. But that does not mean they cannot be altered. Most of the error can be corrected by altering either of these values. This way you can very often find an acceptable solution.