For a lab, I'd worry some about temperatures, given that their coat is light to medium (as opposed to something like a Siberian or Newf). I would also think that they'd be more affected by wind. I try to leave nails a little longer in the winter for a crampon effect. You might want to consider a set of packs or a nylon coat as a wind-block layer.
I always carry one (two in winter) sets of booties. Whether they get used depends on conditions. The harder the snow, especially if there's ice or an ice crust, the more abrasive it is to dog paws. After an ice storm, with sharp shards of ice cracking off twigs and branches is the worst. We make frequent stops to check that paws are doing okay. I find that an area that bears watching is especially the edges of the toe pads, the second worst is the nail bed. Get them used to booties first at home, then on daily outings, before trying to use them on a hike. Once you're out is generally not a good time to introduce new equipment to a dog.
I've heard and tried many things for preventing snow balls. Trimming the fur between the pads is one, but I don't think labs have much fur to trim in that area. I've also tried spray on cooking oils. I've heard about, but not tried, a product called Mushers Wax (Mushers Secret? something like that) on this board. A few people here have used it and speak well of it. I plan to try it.
Because of de-snowballing the paws and frequent paw checks, you may want to carry a warmer than usual hand layer for yourself since you'll be exposing your hands more.
Deep snow is certainly a factor. If it's deep enough, the dog will have to a sort of porpoise jump through it which places a huge strain on the muscles. Luckily, dogs are usually sensible enough to let their humans break the trail for them. A little training can help teach them to stay off the snowshoe tails.
I would advise getting out for smaller hikes in milder conditions, and work up to bigger things. My dog is 2.5 years, last winter was the first winter I had him. We did smaller, easier things - 3-4 miles in all kinds of conditions, opting for easier things if conditions were worse. Earlier this winter we began doing some medium stuff in mild winter conditions - e.g. Lafayette in December. Then we did his first "real" winter hike this past weekend (Tom-Field-Willey, 8 miles, temps around zero, some deep snow, some packed trails, some ice). Watch them carefully, learn what they can and can't tolerate. You'd hate to be out on an 8 mile hike in subzero conditions and have to carry the dog out after 4 miles.