1. Define "cheap". $100 won't get you very far. $300 probably will. Assuming you are operating on the standard definition of "cheap" for this board, the CW around here is:
Deck: Used iRiver H120 "Rockboxed" (~$100), Tascam DR-07 (~$129), Sony M-10 (~$299), Edirol R-09HR (~$299).
I use an M10 and had an R-09HR until I broke it. I like both. I don't know much about the DR-07 but people who use it seem to like it.
Mics: Church Audio CA11, Church Audio CA-14 (both in the sub-$200 range), AT 853/SP-CMC-4 (some selling used around here for $150 or so now)
Pre/Power: Church battery box ($29), Church ST-9100 (~$130), Church CA-UGLY (I don't recall right offhand; less than a 9100), any of the Sound Pros battery boxes (SPSB-x; each hovers around $59-79 depending on feature set).
As I said, for around $300 you can have a really nice rig. For much less, I think your options narrow dramatically. Everyone has opinions, so I'm sure others will chime in.
2. There are posts on here about that that are quite long to repeat, so you may want to try using the "Search" function (it doesn't work great, but give it a whirl; there is a wealth of info. I think there is also a "sticky" at the top of one of the boards, either "Ask the Tapers" or "Microphones and Setup")..
But a general summary is:
Boards usually have three main types of outs:
RCA
1/4"
XLR
Recorders, assuming you get an "inexpensive" one, generally have a 1/8" stereo mini jack input.
So, loosely speaking, you need dual RCA>mini, dual 1/4">mini, and dual XLR>mini. Most common type is probably XLR. Most boards have "tape" outs that are RCA as well, I believe.
Also, keep in mind that board feeds tend to be very unpredictable; not only are they often "hot" and require attenuation on the signal (another accessory) but on their own, they usually are not mixed properly for listening at home. Why? Venues mic and mix for the audience, meaning the board mix usually heavily emphasizes that which cannot already be easily heard in the audience (the smaller the venue, the more true this generally is). So, if you just take a straight SBD patch and nothing else in most small venues, you'll get a mix of mostly vocals a lot of the time. I think everyone on here would tell you that unless you're prepared to invest in a 4-track machine that can mix SBD+mics, you're really better off just using some decent mics like the Church mics.
Hope this is helpful to get you started...