While all of the answers here offer something helpful, there's one thing that can't be stressed enough: you need to shoot from somewhere free of light pollution. Even if you don't have any major cities around for miles and miles and miles, it's likely that there's still some light pollution cast. You don't realize just how dark outside can be, and outhow easy it is to see stars, nebula, and the milky way on a moonless night until you're in a spot without light pollution. It's a stark difference.
My own experience suggests that nowhere on the east coast of the US is ever going to be dark enough to shoot successfully, unfortunately. Even in the North Maine Woods where anything is a few hours away -- let alone a big city that might cause such pollution -- isn't actually that dark. I've discovered this on trips to Wyoming, where I was honestly shocked at how bright the night sky was with no pollution. Capturing wisps of the galaxy was downright easy: a 30 sec exposure at f4 and ISO 3200.
Something interesting about this photo as it relates to this discussion: Jackson is a small town. There are plenty of small businesses and a few big stores, but no skyscrapers, high-rise apartment complexes, or anything like that -- it's a small town. And look at how much light pollution it's casting: you can see it in the photo.