<p>When and how should table stats gathering be performed for Oracle, version 9 and up? How would you go about gathering stats for a large database, where stats gathering would collide with "business hours".</p>

Gathering stats should be done whenever there has been large changes to the data content, for example a large number of deletes or inserts.  If the table structure has changed you should gather stats also.  It is advisable to use the 'ESTIMATE' option.
Do this as an automated process out of business hours if possible, or if you have to do it during business hours then choose a time when there is minimum access to the tables you wish to gather stats for.