The List:
40K Rulebook (Current Edition)- I'll present two legal ways to obtain this: Purchase the hard-bound version (40-60 bucks), or acquire the soft-bound edition that is included in the Games Workshop 40K starter kit called Assault on Black Reach (AoBR). The AoBR box retails for approximately 70 bucks new and you get a small force of Space Marines and Orks, respectively. Also included is the 5E mini-rulebook, dice, three templates, a AoBR starter book, and two measuring sticks. This isn't a bad deal if you want to play one of the included factions; Space Marines or Orks.
However, if you don't want to purchase the AoBR box, you can always find the mini rulebook, templates and dice for sale on Ebay and the Warstore.
2014 Update: Current 7th Edition should have a mini rule book release in August of 2014. Stay tuned! I would even suggest a digital version of the BRB (Big Rule Book) for ease of transport and access.
Tape Measure- If you don't own or have access to one all ready, you can usually find a 16-25 foot tape measure at Harbor Freight for 3 bucks. This game involves A LOT of measuring- get a tape measure.
Template(s)- There are three specific templates that will make your life easier during a game of 40K. A 5 inch diameter circle, a 3 inch diameter circle and an 8 inch conical template. These templates represent a wide variety of weapon and attack types. You don't necessarily have to purchase the plastic templates- you can make your own using a little carboard, plasticard or whatever else you can get your hands on. Following is a link to a page of template patterns that you can use as a guide if you're going to make your own.
Scatter Dice- Six-sided dice where the numerical values' 1-6 are replaced with two hit markers and four
directional arrows. You can purchase scatter dice on Ebay (usually included with regular six-sided dice), or from your Local Games Shop (LGS). Games Workshop sell "dice cubes" with various colors that include a scatter dice, an artillery dice and 26 regular six-sided dice in each cube. GW dice cubes usually retail for 6-7 bucks. If you have access to a thriving gaming community, you will find that guys usually have spare or extra scatter dice, too.
Six-sided Dice (6D)- Make no mistake, you will need A LOT of six-sided (6d) dice. I prefer the 12mm six-sided dice, because their small size is less hazardous to figures and gaming tables, however any size should do. One suggestion made to me was to acquire different colored dice to represent different weapons. For instance, I have a number of green dice to represent Melta weapons, purple dice to signify Plasma weapons, red dice to represent flame weapons, etc. In a game where you may find yourself literally rolling 20 or 30 dice at once, color coding weapons or special attacks makes firing resolution so much easier.
Do you have any casinos near you that offer the game of Craps? Each Craps table sports five six-sided dice with the same serial number at any given time. Due to wear and tear acquired from play, casinos will frequently replace dice sets over the course of a business day. The old sets are canceled then usually offered to patrons. Quite a few casinos will give their canceled dice away- free! Casinos usually sport at least two unique colors of dice and will switch these colors periodically as a security measure. Casinos can be a great source for six-sided dice at a very reduced cost (or even free). Craps dice usually measure 16mm to 19mm in size.
Dice Bag- Have a lot of dice, and no bag to carry them? Get a Crown Royal bag! The bag is purple and made of felt with a drawstring to cinch the bag shut. Any establishment that serves Crown Royal- any store that sells Crown Royal, will often times throw these bags away! Usually a polite inquiry will score you as many Crown Royal bags as you want or need! Now, to be clear this is by no means an endorsement for under-aged drinking! So, before we go any further children, if you're under the age of 21 have your parent or guardian inquire about this for you!
Army Codex (Dex)- There are various playable armies in the 40K universe. Most of these armies have a rulebook, or codex dedicated to them- documenting any special rules, equipment and unique characters to that army. It is a good idea to have your codex handy for rule clarification and dispute resolution. Just an FYI, 40K is currently in it's 5th edition, which means many of the army codices have five editions available. Before you purchase a dex, make sure it is the edition you want!
Army List- It is good practice to have available an army list that shows troop type, relative point cost and any special weapons/equipment chosen. Most tournaments require that you have a list available for each potential opponent and an additional copy for the tournament sponsor/games master for the purpose of review.
Gale Force 9 T.A.C. (Tactical Assault Coherency) Template- This isn't a necessity, but it is like gravy on mashed potatoes, or like the Crown Royal in the Crown Royal bag. Gale Force Nine's TAC template provides a way to quickly reference six inches, 4 inches, 2 inches and 1 inch respectively. As a new player I can't "eye" these distances yet, so this is a great tool that speeds up my game immensely. If you have a few extra bucks, I strongly suggest investing in one of these templates. Last I checked, you can still find this for sale on GF9's website and the Warstore. Over the last year, I have had an increasingly difficult time finding stores that carry this template- be warned.
Gaming Mat(s): Frontline Gaming, along with Tablewar teamed up to provide one of the best ideas to table-top gaming in a long time: The mega mat. There are two flavors (at the time of this writing, 2014)- a 4x4, and a 6x4. The mat is water resistant, and made out of the same material as mouse pads. You are less likely to experience wobbly model syndrome, and, the dice don't tumble as severe in comparison to a plastic table top surface.
Further Consideration:
The Warstore
Frontline Gaming
Gale Force 9
Chessex Dice
Template(s) for 40K and Necromunda