When should you avoid caching, or when is it just too early to bother with it?

I'm building a new service, and honestly, I really want to just slap a cache on absolutely everything. Things are running okay right now, but I'm wondering when does all the added complexity of caching become more trouble than it's worth performance-wise? Is there some kind of golden rule or metric you check before you decide to add caching? I've seen projects get totally bogged down by cache invalidation problems when the data itself wasn't even changing that much. What do you think?