We wanted our pond to look interesting in the winter as well as summer, so we used a lot of evergreens and grasses. We have a Canadian Hemlock tree, evergreen shrubs such as mugo pine, golden threadleaf cypress (they drape over the waters edge really nice), barberry for a red color, holly, boxwoods, birdsnest yew, etc. We leave the grasses all winter and don't cut them until spring.
We filled in with black-eyed susans, coneflowers, autumn joy sedum (looks nice all winter too), daylilies, etc.
Have fun!
Karen