database sharding, how do you deal with datasets that are just getting bigger and bigger

our main user database is getting pretty old. we're noticing read speeds slowing down, and writes are taking longer too, particularly when everyone's using it. we're thinking about sharding it to spread out the work. for anyone who's actually done database sharding, what was the hardest part? did you find any particular methods that worked well for picking a shard key, or for moving shards around as more data comes in