If its going to be painted, I'd use some pressure treated lumber you'd make decks out of. The pressure treated pine comes to mind (greenish tint to it). You can also find plywood for outdoor use too. If you want the look of natural wood, I'd either use cedar or redwood. You can use hardwoods like oak, mahogony, or teak, but that's pretty much cost prohibitive for an outdoor project.
For stains and paints, any outdoor paint from the hardware store would work well. For a top coat, you can get some spar urethane. I think this is a polyurethane that is weather resistant and it also protects from UV. But if you get a chance, I'd talk to one of the guys at the paint counter and see what they have to say.