I was kind of thinking I would still have viable yeast in there, but I didn't put my had all the way down to the bottom to see if the bottom froze.
My point, for whatever it's worth, is that if there was any liquid there there was yeast that was not frozen. Sounds like that's the case.
Do I use more priming sugar than usual? I'm thinking no because of bottle bombs.
You are correct.
I'm thinking I'll only bottle up a 12 packs worth when everything has un-frozen and see how that goes.
Honestly, if you go this direction then bottle all of it up front. If it works then you are done. If not then it may require another touch to add yeast but that's no different than that other half that will be sitting around patiently waiting. Doing the whole batch the same will allow greater consistency. If you get absolutely no carbonation (I would be REAL surprised) then open them all up under sanitary conditions, pour them back into the bottling bucket, and re-dose with yeast. This keeps your beer under (hopefully) sanitary conditions while you wait.
Please note that technically the advice to re-pitch is correct - but the advice I'm giving is what I think will work best for you in the place you are right now. If you have more viable yeast of the same type laying about ready to pitch then by all means do so. I am assuming however you do not, that this being your first beer you are really ready for it to be over and to try the fruits of your work. Waiting to get more yeast is likely not the right answer, and pitching a different yeast can be a complicated matter, so this is the best answer for your position in my opinion.
How long should I wait? I've read a week is a good amount of time to bottle condition, so maybe 2-3 weeks?
Around that. Keep an eye on them. Your first clue may be a re-clouding or more likely a very faint sediment on the bottom of the bottle. I generally like to bottle condition for 2-3 weeks anyway - I think it makes for a better conditioned beer. I'd say a couple weeks after you see some yeast on the bottom before you crack one and try it.
Thanks for everyone's help so far, it's kind of frustrating because I made it through almost the entire process then messed up right before bottling.
We have all been there, the person who says he's never done something stupid is lying. In my last batch I ended up sampling a few too many of my Belgian ales and forgot the whirfloc at the end of the boil. I started brewing in 1991 so you'd think I was over screw-ups.
I learn, I ask, I learn some more, I enjoy it all and that's really the idea.
One of my favorite frozen beer episodes ... I made a double-decocted doppelbock many moons ago. I forgot about it in my lagering fridge and over the winter it froze solid it looked like (although it was in a carboy so it could not have been all ice). I was so disgusted I left it there thinking I would clean it up later. In the spring I went to lager a new batch, opened that lagering fridge and there it was, still waiting for me. I tasted, it was awesome, I bottled (this was before I knew I HAD to re-pitch) and in a couple months I was rewarded with an excellent, bottle-conditioned lager. "Refrigerator" was one of the best doppelbocks I ever made, and it won BoS at three competitions.