Where Can I Legally Ride Off Road in the UK?
In England, Wales and NI You can legally ride in lots of places:


On any bridleway
On any Byway open to all traffic (BOAT)
Restricted Byways (Used to be called RUPPs)
Permisive Bridleways
Dedicated MTB trial centres (of which there are now lots)


The first three categories of path can be found on your OS map, although the definitive maps are held by local area councils and the OS map can (very rarely) be wrong. Permissive Bridleways are open to bikes but are not often marked on maps, they are there with the permission of the land owner and aren't a statutory right of way.

In Scotland the rules are differnt and much more liberal - if there is a trail then you can probably ride it.  There is a good overview here as to the position in Scotland.

A good way to find your local routes is via your local cycling club if they have an off road section.