1. Where would he apply for a UK visa? He's not a legal resident here, so would he have to go back to his home country to apply for a visa? How long would that take?
British diplomatic posts as a policy do not issue visas to an applicant who is not legal in the jurisdiction they serve. Further they do not issue visas in a category leading to settlement (permanent residence) to those who are not legal long term residents of the jurisdiction (i.e not visitors even if they are legal). Exceptions may apply under the most compelling of circumstances such as a natural disaster in your home country resulting in the closure of the visa posts. Your spouse needs to go to his home country for the visa. Normally if successful the applicant is granted a 2 year visa (aka probation visa) and can reside in the UK with full employment rights. 28 days before the expiry of this visa the applicant submits an application for Indefinite Leave To Remain (the formal term for settlement). The form must be signed by both the applicant and the sponsor to the effect that the marriage is subsisting with supporting evidence. On the plus side if your marriage has been of at least 4 years you will be granted Indefinite Leave To Enter (where a settlement visa is granted outside the UK).
2. Does the deportation order from the US have any bearing on his UK visa application? I know there's a space for it on the application, but how seriously do they take it? Do they look at the details of the case, why it was denied, etc?
It would be an issue if there are any serious criminality issues. The UK like other nations does not want 'undesirables' and the immigration rules facilitate the refusal of a visa to those whose presence in the UK is not conducive to the public good. Review the family immigration forum for the level of quite substantive evidence you need to submit.
As a side (but crucial) issue if your spouse ever intends to return to the US (I presume as a USC you have various ties there including family) he needs to resolve the deportation matter before his departure. I presume you have an attorney with whom it be might be worth looking at voluntary departure. This negates any issues over bans and inadmissibiilty waivers. Such will also facilitate you sponsoring him in future to return to the US as a LPR if you so wish.
Good luck
