When in doubt, try a cheap experiment.

Make a list of various forms of recreation, then do one of them for some amount of time whenever you feel the need to take a break. Afterwards, note how well-rested you feel and how long you performed the activity. It shouldn't take many repetitions before you start to notice trends you can make use of.

Although to be honest, the only conclusive thing I've learned from trying that is that there's a large gap between "feeling rested" and "feeling ready to get back to work on something productive".

Anyone offering a single, specific "best" way to rest is likely to be committing the typical mind fallacy. For example, there are people - extroverts - who "unwind" after a work week by going out to clubs. As an introvert, I have a knee-jerk inclination to suspect such people of genuine insanity, because such an activity would have no relaxing or energy-restoring effect for me. Of course, they are no more insane than I am, just psychologically different, but those differences can have a big impact.

As wgd suggests, you can experiment to figure out what is most relaxing for you. Another possibility: if you could provide more details about your own psychology, people who identify with those details could offer their preferred methods. Without more information, I think we will just be other-optimizing.

For knowing when and how long to take a break, the Pomodoro technique is worth a try. You basically alternate between 25 minute work sessions and 5 minute micro-breaks. The breaks are too short to actually do anything in, just step away from what you're doing (probably on a computer terminal), walk about a bit and space out for a couple of minutes. Start with the default technique, then adjust the intervals to see if something works better.

A lot of my idle time goes to browsing the web, but I do worry occasionally that there's something to Alicorn's experiential pica idea, and browsing vapid stuff is just a self-reinforcing cycle of uselessness.

It might be also useful to separate breaks as switching gears and breaks as rest. Running and concentration-intensive meditation can both require exertion, but they're also quite free of the sort of demanding decision-making you need to do when working, and could be considered rest along that dimension. The exercise aspect will also hopefully boost your physical and mental stamina. I don't know what's the good amount to spend running or meditating though, but at least both activities have reasonably natural session lengths (time to run some familiar route, around 30 minutes meditating), so it's simple to do something like 1 session a day or a few sessions a week, and end up with probably not that bad parameters. (On the other hand, I have a hard time figuring out what kind of bodyweight exercise routine is long enough, so I end up doing nothing at all.)

I like to do something physical to take a break from intellectual pursuits- sailing, or hiking usually.

It seems like physical tiredness and mental tiredness are mostly non-overlapping: I can go hike all day and then come back and work at a desk without fatigue, or vice versa.

I'd suggest doing something you enjoy and doing it consciously as a reward for the work you did. Doing boring things might deplete your willpower and is not relaxing.