"Cache" can refer to one of many different types of caches that Kodi uses, and most are not directly related to each other.
A cache can refer to any data that is locally saved on the Kodi device and used for fast access to that data. The overall concept of a cache is explained on Wikipedia:Cache (computing).
Unlike other pages on the wiki that describe a specific feature or how to get something done, this page is dedicated to helping dispel some of the myths and mystery around the different types of caches that Kodi uses.
Video cache and the source of most "out of cache" messages
The video cache is the most common cache that people talk about when it comes to Kodi. The video cache works by saving a few seconds of video before it is needed, so that if there are small slowdowns or bumps in loading the video, it will not constantly pause while waiting to get enough data to resume playing back. The video cache is normally stored in RAM and erased on the fly, as needed. It requires no user intervention to "empty" this cache.
A warning about the cache filling up does not actually mean that more cache space is needed or that the existing cache needs to be emptied. The warning box is not currently well worded and has lead to a lot of confusion with users. What it means is that the video is loading too slowly for the cache to smooth out all of the bumps, and that the bumps will keep happening due to that low video speed.
Kodi only uses a tiny amount of RAM for the video cache, about 60 MB. This is because Kodi is not currently coded to see if the hardware you are using has more or less RAM, so to be safe only a small amount is assumed to be available. Users are able to increase this amount, and modify how "quickly" it fills up, by following the guide at HOW-TO:Modify the video cache. However, changes to these settings are only helpful for a few situations, such as a network that fluctuates in speed, occasional wifi interference, or a connection that is borderline too slow for video to playback.
Note: No amount of video cache tweaking will make a slow server connection any faster, which is a common issue for people who stream over the internet. Even if you have a fast connection on your device, it doesn't matter if the connection on the other end is slow. The server itself might not always be slow, but might be more busy at different times of the day.
A lot of people see references to a "zero cache". This is a specific setting for the video cache to use local storage (such as a hard drive) instead of RAM. This setting is not needed for most users, even if you only have 1GB of RAM total.
Note: The zero cache mode/settings does not improve the video cache performance.
Users should not use the zero cache mode/settings on a device that does not have a lot of free internal space, such as an Amazon Fire TV, OUYA, or other devices with only about 8GB of local space total. Such devices will only have about 4GB of available space when you deduct the OS and other files that are used, and this is rarely enough space for a full length movie. If Kodi attempts to use the local drive without having enough space then video will either suddenly stop, or Kodi could even crash.
Like all video cache settings and modes, the user does not need to manually "empty" the cache when using the "zero" setting. Kodi will automatically empty such temporary files. If Kodi crashes then it should clean up the files the next time Kodi is opened.
Some (but not all) add-ons will save files to make their own "cache". This can be for many reasons and be used for many different types of files. Some add-ons will even bypass the normal video cache (described in the section above) and implement their own special video cache, by pre-downloading files and then playing them back locally. This method isn't necessarily wrong, but it depends on the add-on keeping track of those downloaded files and cleaning them up, or else the device will run out of available memory.
Many add-ons do not always clean up these files, and as a result some people have used various tools too "clean the cache". Because the only known add-ons that have these issues are ones that break the community rules for the official Kodi websites, we cannot help users who need help with this situation. The only advice that can really be given here is that you should avoid using add-ons that are unable to clean up after themselves. If you do need to clean up such files, there is information on the internet for doing so.
For any situation where you need to clean up leftover add-on data files, you can also manually delete various add-on files by going into the File manager and navigating to the userdata folder (which will be labeled as Profile directory) and then into the addon data folder. Find the add-on in question, and you should be able to manually delete files inside that have collected over time. Be careful to not delete anything important, such as a settings file for an add-on you still wish to use. The exact contents of these folders vary greatly between add-ons.