Usually 1,000 people for a state poll and between 1,000 and 3,000 for a nationwide poll.
The state polls are usually done once a week for lean states, and up to every second day for toss up states. The nationa polls are done every day as a rolling average (so the past 3 days are average to smooth out errors).
The polls are weighted to account for the correct number of democrats, youth, elderly, blacks, etc. Polls that don't weight like this often give the inaccurate results you see floating around (like any national poll currently not giving Obama at least a +4% lead).
A poll's results are as important as its trend. If the poll just went from +4% McCain to +4% Obama in a week even though other polls say +8% Obama (from a 0% tie in a week), then there's likely nothing inherently wrong with any of these polls.
Margin of error ranges from +/- 2% to 5%, usually. But for national polls you can largely ignore this, since they do rolling averages and update daily - so it's easy to see outliers.
At the end of each poll it will tell you how many people were sampled and what the margin of error (MOE) is.
This link rates pollsters according to accuracy and consistency:
http://www.fivethirtyeight.com/search/label/pollster ratings
The above site just downright excludes some polls, though, because they are done by people with a vested interest (usually Republicans).