Should I cache the data or hit the database?

Question

I have not worked with any caching mechanisms and was wondering what my options are in the .net world for the following scenario.

We basically have a a REST Service where the user passes an ID of a Category (think folder) and this category may have lots of sub categories and each of the sub categories could have 1000 of media containers (think file reference objects) which contain information about a file that may be on a NAS or SAN server (files are videos in this case). The relationship between these categories is stored in a database together with some permission rules and meta data about the sub categories.

So from a UI perspective we have a lazy loaded tree control which is driven by the user by clicking on each sub folder (think of Windows explorer). Once they come to a URL of the video file, they then can watch the video.

The number of users could grow into the 1000s and the sub categories and videos could be in the 10000s as the system grows.

The question is should we carry on the way it is currently working where each request hits the database or should we think about caching the data?

We are on using IIS 6/7 and Asp.net.