How do horizontal and vertical lines affect viewer's perception of composition - do they have some unique connotations or are they just opposite of diagonals?
Vertical lines tend to imply strength and power (think supporting columns of a structure, tree trunks, things standing or growing, reaching up or out)
Horizontal lines tend to imply calm, balance or stability (think horizons, oceans, landscapes in general, things at rest)
In addition to Mike's answer, horizontal and vertical lines are also often used as indicators of division and separation or joining and linking. For example, a shot of a small dock head-on, which appears as a fat vertical line, signifies the joining of a shore with the rowboat at the end. The horizontal line of the horizon is the most ubiquitous example of a horizontal division, between land and sky.
In addition to MikeW's answer, horizontal/vertical lines can be used as framing devices, retaining the most area for the actual subjects of the photo. (as opposed to when you use diagonal elements as framing).
I'm talking about things like trees' trunks, door/window frames, walls, ceilings, etc. A bit specific, maybe, but it's a technique with pleasing results!
Horizontal and Vertical lines together can be used in composition for something called 'The rule of thirds', Which itself is a rough approximation of the Golden Section (1.618 or about 2:3).
By dividing your frame in two three equal Horizontal and Vertical sections (imagine a grid with nine sections created by two Horizontal and Vertical lines) & placing your point of focus (the subject of your image, not necessarily the point of sharpest focus) along those lines or at the intersection of those lines one can influence a viewers eye as they view your image.
Those sections can further be divided into more squares or triangles (Diagonals) to further influence a viewers eye as they view your image.