Let me answer the question by amalgamating suggestions made by several posters throughout the already provided answers and comments. Hopefully these suggestions taken together will help yield the best possible results.
- Know where the Milky Way is
Obviously, knowing which way to point the camera is important, but actually spotting the Milky Way with your eyes is next to impossible. Know where the Galaxy is in the sky by using recognizable constellations as landmarks. There are programs that can help you familiarize with the sky including Stellarium, Google Sky and for Android Mobiles SkEye, to name a few. There are quite a few available.
- Choose a time and a location
In order to capture the best image there are some important factors to consider. You need to be away from light pollution, so select as remote a location as possible, away from city lights and other significant sources; a cloudless night with no moon. You can Google for moonrise and moonset times. Generally, avoid nights with a full moon. When the moon is waning (after full but before new moon) it will be absent from the sky for the first few hours after sunset, and if it is waxing (after new but before a full moon) you will do best to shoot in the morning hours. Best yet, shoot during a new moon. It won't be in the sky at night.
Also choose arid conditions over moist; directly after rain is a good time. And prefer high altitude locations to lower. The atmosphere is thinner the higher you are and will have less of a distorting effect on the stars.
- Select a lens
You will most likely want to get at least a 40 degree field of view in the frame so you don't want anything more than 50mm for a full frame or around 30mm for a crop sensor. Faster lenses (larger apertures) will allow you to choose shorter shutter times to minimize star trails, and so will wider angles (shorter focal lengths).
- Select the correct exposure
Obviously you want to maximize the amount of light you're working with, but there can be trade-offs for each of the dimensions you have to play with: ISO, shutter speed, and aperture.
First, select your largest aperture, then I would say, choose a shutter speed. Star trails will be a problem when the shutter is held open for more than a few seconds so there is a balance between minimum trails vs maximum light. You can use the rule of 600.
Basically:
shutter speed = 600 / focal length (for full frame sensors or)
shutter speed = 400 / focal length (for crop sensors)
But the lower, the better for the sharpest image possible.
Then select the ISO that will work with this by using the following formula:
ISO = 6000 * f-stop^2 / shutter
For example:
crop sensor, 15mm lens, at f/4.
shutter = 400 / 15mm (approx. 26s)
ISO = 6000 * 4^2 / 26 (approx. 3692 so choose ISO3200)
At least, that's a good starting point. experiment from there.
- Shoot
Above all, have fun.
Update: - optionally, use post-processing
This will only be possible if you consider yourself a mathematically inclined computer programmer. I recently came across this amazing post from flickr user magnetic lobster, who took multiple 20s photographs and combined them with a mathematical algorithm. This worked incredibly well, even over the bright lights of a big city. Lots of details about his procedure are included.