Four-Post Overhead
If your deck is small and your overhead will span its entire surface, you can support its upper structure with posts extended from the railing system. In this configuration use through posts supported in footings. To simplify construction and save time and money, use a single-post corner instead of a double-post design. In all other cases a four-post overhead will have at least two posts supported by the decking and the framing under it.
In a new deck, plan the location of the posts and include specific details of the support structure in your detailed plans. Retrofitting an old deck requires some forethought too. You'll have to remove a portion of the decking to gain access to the joists.
Overhead structures do not have to support a live load, but use the live-load span tables when computing the size of the lumber anyway. That way you won't have to worry that the upper structure will sag under its own weight. Many overheads use a doubled 2x beam fastened to the sides of the posts. This construction is strong enough to support the structural load and avoids unattractive framing connectors. Use carriage bolts and countersink the nuts for a better look.
Prestart Checklist
Time
About 12 hours for a 10x12-foot overhead, more with decorative cuts
Tools
Tape measure, speed square, circular saw, framing square, framing hammer, chisel, ladder, cordless drill
Skills
Measuring, cutting, fastening
Materials
2x, 4x, and 1x lumber, carriage bolts, machine bolts, washers, nuts, fasteners