At how many battery cycles should I consider replacing my battery?
You haven't mentioned what's the model of the Mac you are using, Apple's Determining battery cycle count for Mac notebooks  will tell you more about the Charge Cycle.

Also in case you are still in warranty, which I assume you are not cause of so many charge cycles, you can go to the Apple Store and get the battery diagnosed, if they find a problem they will replace it.