Texas Water Lilies (google it) has many varities and cheap. I have seen some local stores sell ones for $20 each - TWL has them for $5-10 for grown plants. The problem we had, was older pond, but still very clay soil and compacted hard. First year, almost none took. Next year, we put in burlap bags per previous reply with nice rich topsoil and brown "muck" and weighted with rocks (and put a couple slow release miracle grow fertilizer sticks in the bag also. Grew nicely until the migrating geese found them and it was all over. I tried again with wild lilies I got from local lakes (need to take the root/rhizome). These also grew well, but disappeared later in season, presumably from the geese eating them again.
My pond (actually) my uncle's, has the opposite problem of most people - we can't get any plants to grow consistently and it is illegal to shoot the geese by us. I was almost considering cattails (even though they are very invasive) just to get something to grow.
Anyway, good luck and the burlap bag trick worked well to get them started
