Wilderness survival might be a better place to look for "finding north without a compass" than in robotics, but here are some electronic adaptations of those techniques that might actually work on a robot.
Of course, your first choice would be to use a GPS -- the line between each pair of fixes will give you your direction of travel (but it won't work while you're standing still). If you want something that works while you're standing still (and your vehicle is large enough), you could just use 2 GPS units spaced as far apart on the chassis as possible and measure the angle between them.
(Full question here: https://stackoverflow.com/questions/8123049/calculate-bearing-between-two-locations-lat-long)
This is by far the easiest and best way, but to make things really interesting, here are some other possible-yet-impractical approaches.
Have the robot use its camera to watch its shadow for 10 or 15 minutes, and note the movement of the shadow. Making a robot able to recognize its own silhouette is a problem in itself, but this is certainly an interesting thing to do with computer vision!
Analog Watch Method
If you can point a camera at an analog watch, you can take advantage of the fact that the hour hand makes two revolutions in 24 hours (while the sun only makes one). If you just make an analog clock of your own that rotates once every 24 hours, you can just point the 0:00 mark at the sun and the arm will point north. It won't work at night.
Once you find north using the sun, you'll have to keep a good estimate of where it is while moving -- weather and time of day would prevent you from measuring it continuously. There are a few ways to do this:
Again, the best possible option. A pair of GPSes would be even better.
Inertial Navigation Systems can give you a decent approximation of angular position by doubly integrating the (measured) angular acceleration. You'll inevitably accumulate errors over time, but you can mitigate those errors by buying progressively more expensive INS units (seriously, they can cost into the tens of thousands of dollars). Assuming you know the initial heading, the INS can track it from there.
You could use visual landmarks to keep a sense of which way is north. Since you said it was a featureless environment, that's probably not going to work. On the other hand, I don't know of any places in the great outdoors on earth that would count as "featureless". Here is one possible resource for that: http://www.cvlibs.net/publications/icra11.pdf
You could also drop your own markers, and use surveying techniques to keep your bearings.