One challenge associated with implementing control algorithms on spacecraft operating in low Earth orbit is that it can be difficult to tune the gain parameters for ideal system operation. Many standard approaches to gain optimization, such as pole placement or linear quadratic methods, are not applicable for the large-angle reorientations that many spacecraft undertake. Furthermore, it is desireable to develop a strategy for gain tuning that does not require linearization of the system equations or other approximations while still maintaining computational efficiency. To that end, this paper presents a comparison between three different strategies for tuning the gains of a nonlinear, almost globally stable control law. Previous results have demonstrated the almost global stability of this control law by means of Lyapunov-type methods on the nonlinear space of rigid body rotations. With stability established, the gains of the control law are optimized for a large-angle "detumble" maneuver by means of trial-and-error search, a gradient optimization technique, and implementation of a genetic algorithm. It is shown that in general the genetic algorithm is able to search the design space more efficiently than the other methods, and is not subject to settling on local optima.