Leaves WILL fall and get into the pool...no matter what you plant. No plant has immortal foliage. So-called "evergreen" plants shed their leaves incrementally throughout the year; deciduous plants shed their leaves en masse in November or December. That's the only difference. If keeping the pool free of debris is of paramount importance, then you don't want a tree near it. Maybe a plant with rather few and sturdy leaves like Phormium 'Guardsman' or Cordyline 'Red Sensation' or a fronded plant such as a palm or cycad would better meet your needs. We'd need to know more about your climate in order to make specific recommendations.

How wonderful for you- you must be really excited. What style do you like? Japanese, cottagey, native, tropical?

I believe Japanese Red Maple might need shade. I have not been able to grow them in full sun, especially not with concrete or masonry nearby reflecting heat.

All trees will drop something in your pool. One tree that is often used because it stays small and is not so messy is Japanese Black Pine. Another one that I like is Tolleson's Weeping blue juniper.

My white Fringe Tree is very pretty and is less messy than my other trees, but conifers might be your best bet near a pool.

Renee

I like both of those trees. Doesn't Pawlonia get big, though?

My parents had a dwarf black pine that laid over on its side then grew back in a "C" shape. It never got taller than ten feet, and it was just lovely.

You may also want to look at Chitalpa, and yellow Tabueia.

Here's a pic of flame tree, another favorite of mine:

http://www.google.com/imgres?imgurl=http://www.allnatives.com.au/images/flame_tree%2520various.jpg&imgrefurl=http://www.allnatives.com.au/trees&usg=__2wqRmSnboglPpYlKhEOkYsg9xH8=&h=262&w=200&sz=38&hl=en&start=6&um=1&itbs=1&tbnid=yClFrGJGsltcmM:&tbnh=112&tbnw=85&prev=/images%3Fq%3DFlame%2Btree%26um%3D1%26hl%3Den%26sa%3DG%26tbs%3Disch:1

Another small tree that is very pretty is the Mayten Tree.

Renee

Here is a link that might be useful: {{gwi:545288}}

This tree will be the centerpiece for the whole yard and sit right next to our pool and spa.

What kind of pool? How close to the pool? Be careful not to damage the pool with invasive roots.

Zeuspaul

The tree will be near the pool. We intentionally were careful to fun pipes away from where the tree will sit.

Leaves will potentially be able to fall off into the pool.

The Pawlonia (Empress Tree) will grow very fast, and cast a lot of shade. It's not a tree to garden under, between the shade and the root system.
I like the look of the evergreen Arbutus 'Marina'. 4 seasons of interest - bark, leaves, flowers and "fruit", but not messy.

We intentionally were careful to fun pipes away from where the tree will sit

I was concerned about the pool itself. If it is concrete it may weep some moisture and draw roots which can damage the pool.

Zeuspaul

Check the Sunset Western Garden Book: they have a section on "what to plant around swimming pools".

Japanese Maples need a shady location. They are understory trees (they naturally grow in the shade of larger trees) and do not like full sun.

If you want something truly spectacular and have a large budget, a tree Aloe such as A. barberae. Nice and clean.

Any tree with showy flowers drops a lot of litter. Some flowers such as Jacaranda also create a slipping problem on concrete. Factor that into your decision.

Heres an A. barberae aka A. bainseii

Here is a link that might be useful: {{gwi:545290}}

Wow, hoovb, did you see the flower coming out of that teeny weeny succulent at the base of the Aloe? My gosh!
Renee

Gorgeous trunk on the Tabueia. I've never heard of this tree.

Weeping cherries are certainly conversation starters but not sure this is a good choice for your location.

I believe some sort of Palm Tree will be the best for your situation.
Whomever said Arbutus marina was not messy doesn't have one. I do. It sheds leaves all summer and drops messy fruit all winter and drops flowers like crazy. I love it and it's a gorgeous tree, but I would never plant this tree near a pool.

I second the advice of looking at the Western Garden Book, they also have a 'Plant Finder' on their website. Under the advanced search option in 'Problem Solvers' they have 'plants for around pools,' check that and 'trees' and enter your zone and you should get a good list of options.