Materials
I generally make my game boards out of a light-colored poster-board. A quarter sheet or half sheet is generally large enough, though obviously that depends on the game and on the size of the playing pieces. If you want, you can also glue on a backing (like cardboard or a mounting board) for added sturdiness, though this will make it very difficult to laminate.
I usually start by outlining the design elements (squares, pictures, and lettering) lightly in pencil, then go over them with a magic marker. Coloring the board is a family project with which we have a lot of fun. After the board is done, you can get it laminated to prevent damage through accidental spills.
Basic Layout
Here are a three examples that illustrate some different types of layout:
The board on the left, from "Race to Altair," is sequential. Players begin on square 1, on the bottom left, and move clockwise until they reach the center, the planet Altair. The center board, which is for "Space Battle," is open; the playing spaces are not connected in a particular pattern. It also uses hexagons rather than squares, making it a "hex" board. (Hexagons are really hard to make with a ruler, so I printed out several sheets on the computer, then pieced them together ... a fairly laborious process, but it worked. You can also purchase hex sheets from game stores.) The board on the right, which belongs to "King Richard's Ransom," is a hybrid. There are six different areas connected by paths; movement is neither completely sequential nor completely open.
Each format works well with a particular kind of game. For example, strategy games often require "open" boards, while "sequential" boards are good for racing games.
Hybrid boards are the most fun to design. In "King Richard's Ransom," I wanted to spread out the different areas that I knew my son would enjoy the most (tournament, castle, and forest), just so that he'd have to traverse the board. Moving from the tournament to the castle means going through the town or cathedral, which he otherwise would never visit.
Finishing touches
Once you've decided on a layout, you can also add other design elements. For example, the "Race to Altair" board has "warp," "black hole," and "bonus spaces." Players that land on these move ahead or back a certain number of spaces (move ahead/back) spaces, or they get a card that exempts them from the effect of landing on a "black hole" space. Similarly, when ending a move on a squares marked with a "?" in "King Richard's Ransom," players draw an event card. I also often place obstacles on the "Space Battle" board which make coordinated movement more difficult and require some strategic thinking when there are many pieces to be moved.