When designing a new recipe, there is often a particular style that a brewer has in mind; witness the number of requests for "clone" recipes that get posted here. A book that I find invaluable when trying to invent a recipe for a style I haven't brewed before is Fred Eckhardt's The Essentials of Beer Style. The main section of this book is a self-described "beer catalog", with brewing profiles for 38 catagories of beer. These profiles contain original and final specific gravity, color, hop bitterness, and alcohol content for several commercial examples in each of the catagories. Other references that I consult are the Zymurgy Yeast and Hop special issues (and now also the latest Beer Styles special), and Dave Miller's The Complete Handbook of Home Brewing.
Generally, building a new recipe involves selecting the appropriate kinds and amounts of malt (for flavor, gravity, and color), selecting the appropriate variaties and amounts of hops (for bitterness, flavor, and aroma), and selecting the appropriate yeast (for attenuation and flavor).
As in all facets of homebrewing, malt selection is always subject to the brewer's discretion. My flexible rule of thumb is to use British pale malt and optionally crystal and dark (chocolate, black) malts for British ales (pale, brown, porter, stout); American 2-row (the widely available Klages) in place of the British pale when doing American microbrewery styles; and Klages, Crystal, Vienna, and Munich malts for Continental lager styles. A wide variety of crystal malts, from 20L to 120L color, are available to allow the brewer to adjust the caramel sweetness and color of the finished beer. Getting the malt flavor that is appropriate for the desired style is often a matter of getting the appropriate proportions of specialty malts; again, Eckhardt gives lots of hints. For example, for Bock/Dopplebock, Fred suggests dark Munich, dark caramel, dextrin, and black malts for darker color and sweetness. Black malt is convenient for adjusting color for dark beers, as 1 or 2 oz of 500+ L malt can make a great difference in color with a minimal flavor impact.
For roughly calculating the color of the finished beer, one must know the color (in degrees Lovibond, L) of the malt one uses in the mash. Color of typical beer malts runs from less than 2L for pale lager malts to greater than 500L for black malt and roasted barley. If your supplier isn't providing the color of your malt, you may want to ask him if he can do so. On pp. 54-55 of Miller's book there is a table of malt colors from Briess Malting, and a formula for calculating wort and beer color from the colors and amounts of malt used. For extract brewers, you're pretty much on your own. If any extract brewers have some emperical numbers for colors of malt extracts, you may want to share them with this group. Miller's formula will result in a color in degrees Lovibond; unfortunately, Eckhardt's profiles give a color value on a 1-10 scale, with a mapping from his 1-10 to the SRM degree, which he says is roughly equivalent to the Lovibond degree. For example, he says that Ayinger Export Weissbier is color 4, and his table says that 3.5-4.5 is "light amber", 5.5-10 SRM. I usually look at several examples of the style that I'm trying to brew, and get a rough idea of the SRM color I want from Fred's book.
Calculating original specific gravity is a matter of knowing how many points of specific gravity you get per pound of malt per gallon of water for your particular process, and then calculating for the combination of malts that you're using and the size of the batch that you're brewing. Miller (on p. 196) and Papazian both give points/#/gallon figures in their books. Miller's tend to be quite a bit higher than Papazian's. Grain brewers will have to brew a few batches to get a feel for how well they extract malt sugars from their grain, and use the values that their particular process gives them. Extract brewers are probably pretty safe in assuming that the numbers in Miller's book are accurate, as one should expect to get 100% efficiency when using extracts.
Selecting hops is another personal decision; typically one will use English Goldings or Fuggles when doing British ales, noble Continental hops for European lager styles, and popular American hops (such as Willamette or Cascade) for micro styles. Again, this is wide open, and many brewers will also find use for the super-high alpha bittering varieties that are becoming popular (Eroica, Chinook, etc.). Whatever hops you decide to use, you'll need to know the alpha acid content in order to calculate the bitterness contribution from the hops. Again, if your supplier doesn't provide this information, request that they do so. Eckhardt's book gives profile bitterness in IBU (International Bittering Units). Formula for computing IBU from alpha acid content are available in several references available to the homebrewer; those that I know of are Eckhardt's Beer Styles, Rager's article in the Zymurgy Hop special issue, and Byron Burch's Brewing Quality Beers. Using any of these to compute bitterness, and comparing to the profiles in Eckhardt, there is no reason to be under- or over-hopped for the desired style. For extract brewers using hopped extracts, there is a table of many of the more popular hopped extracts, with bitterness values, in the Zymurgy "Hops and Beer" special issue; unfortunately they are in the infamous "HBU" units. A little math should be able to get you to IBU's.
The other issue involved in hopping is bitterness vs. flavor and aroma. Long hop boils are necessary to extract the bittering acids from hops, but this tends to drive off volitile flavor and aroma compounds. Late additions are used when hop flavor and/or aroma are desired. Rager's and Burch's IBU formula have utilization factors for late additions. I know of no way to quantitatively measure the aroma and/or flavor contibutions of late hop additions. You'll have to experiment with this until you get the desired effect. Eckhardt's book hints occasionally when a hop flavor or aroma may be appropriate; also note than German (lager) brewing practice often calls for 3 separate hop additions, while British (ale) brewing adds all hops at the beginning of the boil. Aroma may be added later by "dry hopping", a topic frequently covered in this digest.
Finally, one chooses a yeast. For Wyeast users, the names of the yeasts make it pretty easy to guess which one might be best for the style you're brewing. An article by Burch in the Zymurgy yeast special goes into a bit more detail describing the character of many of the Wyeast varieties. If you're using dry yeast, your choice is more often limited to a couple of brands, and "lager" or "ale". Use a yeast that you're comfortable using that provides results with which you're happy. If you know anything about the the degree of attenuation to expect with your choice of yeasts, the final specific gravity information from Eckhardt's book and/or sweet/dry descriptions of the styles can help you select an appropriate yeast.
When you put it all together, you'll find out that things like wort specific gravity affect hop bitterness utilization, and you might discover that computing all of this stuff becomes an iterative, fine-tuning process. Fortunately, there are ways to make this easier. There are a couple of free spreadsheets floating around that include the formulas that I've mentioned. I use one for the Unix "sc" spreadsheet and wouldn't do it without (thanks, Tom). There are also commercial software programs available for home computers, check Zymurgy for advertisements if you're interested. I believe that Darryl Richman's program for the Mac does all of this and more, including water chemistry if you're interested in fiddling with that.