Well depending on what CPU you are talking about, some caches have their own multiplier and can be "overclocked" independently of the core clock. For instance Haswell. With Haswell, the L3 cache has it's own multiplier. In all overclocking guides I've read that you should keep the cache multiplier so that it's within 300MHz of the core clock. The L3 cache is the slowest of the three levels of cache on Haswell, L1 is the fastest and L2 is slower than L1 but faster than L3.
Older CPU's usually clock their cache based upon some set multiple of the base clock and therefore when you increase the CPU clock, you increase the cache clock proportionately.
In most cases the data the CPU needs will be sitting in one of the two first levels of cache which is the fastest. If it's not in the cache it looks in first that is registered as a cache miss. Obviously cache misses have an affect on performance. At the very least a CPU designer hopes that his design predicts what data is going to be needed and have it stored in at least one level of cache as access to RAM or storage is very expensive.