When does sharding actually make sense for scaling a database?

We've been talking a lot about scaling our database and sharding keeps coming up as a solution. On paper it makes sense for handling huge loads and distributing data. But I'm trying to figure out the real downsides and when it actually becomes worth making things more complicated. Is it just for when you're super big, or are there times it makes sense sooner than I'd think? What kind of headaches does it cause that you wish you knew about earlier?