Hi Dalton and welcome to GoY. Sorry to disappoint you but most councils have a bye-law which states that a hedge can not be taller than 2 metres.

Climbers would grow fastest but will only cover up to the height of existing fence and need supporting to acheive more height.Looks like a hedge would be the best option,but unless planting expensive mature plants this will take a few years.

Do you need the same amount of privacy in summer and winter. I have planted eucalyptus trees to give me the required height because there is no restrictions on trees. I plan to keep it pruned so I get only young foliage. They grow up to 4ft. a year. They will get out of hand height wise if they are not pruned regularly every year.

Thanks for your advice. I didn't realise there are restrictions on hedge heights, it looks as though trees may be my best bet.

As for the eucalyptus, I don't know anything about thus tree so will need to do some research. You asked if I need privacy in winter too, does this mean it is not evergreen?

Do any of you have any knowledge of the silver wattle tree?

Yes Eucalyptus is evergreen but you would have a wider choice of small trees if you felt the privacy would be covered by deciduous trees in the summer months when you would be using the garden. At the same time the branches of deciduous trees cut down on wind etc. even when they are not in leaf. I'm thinking of trees like the Amelanchier Canadensis or the sorbus (rowan). Karensusan did a very good blog recently on small trees in her garden for privacy. I like the eucalyptus because it has an open framework similar to the birch tree but with the added benenfit of being evergreen. It is actually a silver blue colour. The birch is recommended for dappled shade, I think the eucalypus is similar. The birch is quite late in leafing up in spring.
The silver wattle can grow to 30m I believe so maybe not the best choice but for growers info by uk residents have a look at this link
http://davesgarden.com/guides/pf/go/2499/

Before you start planting trees, it rather depends on the distance between this area and your house - no tree should be planted within 40 feet of your, or next door's house. Eucalyptus gunni is a fast growing tree which will eventually make at least 60 feet if left unpruned, so if you plant one, be prepared to prune it rigorously every spring, and probably again by July, to keep it under control.
Other trees to consider, if you do not mind lack of privacy in winter when you're not actually in the garden, are Laburnum, Crataegus varieties, Malus such as M. 'Gorgeous'. All these are considered smaller trees, but nonetheless, check the spread before buying - a mature Laburnam will have a crown which makes about 20 to 25 feet across.
Consider also larger shrubs/small trees such as Amelanchier 'Ballerina', about 13 feet high, or A. lamarckii, considerably taller. Buddleia davidii is a fast growing shrub which will reach around 10-12 feet in a season, but it does need cutting down every spring. Otherwise, large shrubs would include Elaeagnus varieties, Cotinus coggrygia, neither of which is particularly rapid growing, Cotoneaster 'cornubia' (semi evergreen) and Pyracantha.

Also remember that anything that grows very fast while young does not usually stop growing - it grow fast because it has a long way to go so you would be committing yourself to a lot of pruning work for ever after.
Had you thought of putting a trellis on top of the fence and growing climbers up it? It wouldn't go to 4 metres but it would be a start, especially while your tree is growing. You say "trees" - you don't say how long the fence is but when planting trees you have to allow for the eventual height unless you want to start cutting them down again when they get too big.

Thanks to everyone for your advice! I am now even more confused being very new to this! I am now, after speaking to some friends thinking about planting 'Sorbus' or 'Mountain Ash' trees. I know they are not evergreen but after some research I see that they are quite fast growers and quite dense. Can anyone recommend how closely they should be planted and any useful tips!

Depends on the height and spread of the variety you choose, but you wouldn't want them closer than 15 feet between as a minimum.

Wow! Thanks for the advice Bamboo, I didn't realise they would grow that big! I was thinking of planting a tree for each fence panel! Now I am really showing what a novice I am! A friend suggested the 'red robin' for all year colour, is this perhaps better suited to my needs?

Have you checked out any of the suggestions in my earlier answer? You can google the names I give to see details. The reason I say 15 feet is because the crown or branch/leaf area of a tree will spread 15 - 25 feet, even a small tree - obvioulsy, if you plant them any closer than 15 feet, there won't be room for all the foliage on both trees. But it does depend on the height and spread of the tree you choose.
Photinia Red Robin does get large and is evergreen, so not a bad choice. I'd choose one tree (depending on how long the border is) that has a spread of 25 feet in the crown, then plant beneath and around with taller shrubs. If the border is, say, 100 feet long, then I might use 2 trees, provided they weren't any closer at the root than 40 feet to my house.

Thanks again Bamboo. I have looked at your suggestions and quite like the Laburnham and also comubia, there is so much choice! My garden is around 80ft along the back and I really want to screen it as quickly as possible. I appreciate that I will have to maintain whatever I choose. Decisions decisions....!!

The Cotoneaster cornubia is more a large shrub than a tree, so no reason why you can't have both. In fact, just about enough room for 2 trees if you want, with a spread of 25 feet at the crown for both, plus large shrubs.