It depends exactly what kind of performance problem you're having.
MySQL 5.1's partitioning only allows you to partition the first bit of the primary key. This means that if you want to use any useful form of partitioning, it is often desirable to have a composite primary key.
One of the most common use-cases is for expiring old data, which can be very expensive in non-partitioned cases. In that case you'd have to make the primary key start with a date/time and partition on that.
Then you can expire rows by programmatically dropping old partitions.
Other cases are where your common queries are able to benefit from partition pruning.
Remember that you cannot fix every performance problem with partitioning; it is not magic. For queries which don't benefit from partition pruning, every partition must be queried. MySQL does not do this in parallel, so it is typically as slow as using a non-paritioned table.
- Identify exactly what your performance problems are
- Decide how much improvement would be enough to fix them
- Decide how much performance regression you could tolerate in other use-cases
- Test, test, test and test again on your production-sized data on production-grade hardware on various diferent setups
- Repeat until you're satisfied.
- Perform relevant functional testing; release!