This is a much broader question than you might suppose, because there are so many different types of packaging, some very straightforward, some far more complex.
If you are being asked to design the packaging itself in addition to the artwork that will go on it, I would strongly recommend subcontracting that part out to someone with actual packaging training and experience. Packaging is part engineering, part architecture, part origami and part logistics, and it is n-o-t something you should tackle without specialist help. Just to take one example, getting one dimension slightly wrong could add 15% to 25% to the shipping and distribution costs of the product because it will no longer fit neatly into standard shipping cartons, pallets or containers.
That said, the design work starts once you know precisely how the packaging is constructed and you have contacted the company that will produce it to determine their requirements for artwork.
Flexography is very commonly used to produce packaging and labels, and has very different requirements from regular printing as regards inks and allowance for registration errors. Photographic CMYK color separations may not work, for example. Offset press and digital are much more precise processes, so if you design for offset you may run into problems with Flexo.
[UPDATE March 2015]
Alan Jeffcoat, VP Marketing at Pen & Inc, pointed out to me, complete with a series of recent photos of actual press sheets, that the original version of the above paragraph was out of date to this degree: modern flexo equipment is capable of accurate registration that rivals offset. You'll want to consult with your provider as to their capabilities. Not all shops have the latest (or even decently modern) equipment.
Your package designer or producer will have a dieline file that gives you the precise layout of the "flat" (the package as printed, before folding). Be prepared to print that, cut it out, and fold it so that you can visualize how the artwork will appear. Nothing is more embarrassing than to have one panel printed upside down on the finished product, and that's a very easy mistake to make if you don't create a 3D paper mockup.
If you're redesigning the artwork for an existing package, get hold of one and deconstruct it. That will also give you a great reference to keep you oriented as you build the artwork.
What you'll need from the client are the contact information for their packaging provider, their identity artwork and information about their corporate color scheme, especially spot colors, and the rest of the usual information you'd collect for any design project.
One last bit of advice: at any point in the process, if you have the slightest question about how something needs to go, talk to the client and/or the printer. Don't guess. Even highly educated guesses can be wrong, and when it comes to packaging that can be a very expensive mistake.
Good luck with the project!