We got married in Florida because there was no blood involved...
Basically went down a day ahead went to the courthouse filled in the paperwork, took it to the minister/notary dude, got married, he signed it and back to the courthouse, we signed and poof it was done.
So it was very easy...most places like Vegas or a Justice of the Peace will tell you excatly what you need to do in each state. Our B&B recommended our guy.
I'll leave the spousal visa stuff for someone who knows.