I played several hours a started three different worlds in Minecraft, but I have never found any sugar canes. I read on Minecraft wiki to search near water but still no luck. Do you have more hints? Is it possible to re-create an environment that allow sugar canes to naturally grow?
Sugar cane (and cactus) only naturally spawn on chunk generation. Sugar cane grows on dirt/grass next to water. The easiest way is to generally walk along a coastline or riverside, and hope you find some.
They're not all that rare for the most part. Use something like Cartograph G to list how many pieces are in your world; maybe you just haven't got any generated yet?
Once you've got one though, you won't need to look for any more, they are extremely efficient to farm!
How old is your map? When I started my first map, in Alpha 1.1 it was a lot rarer than it is now, although I don't know when the spawn rate was changed.
Sugar cane only grows on grass/dirt/sand adjacent to water (not diagonally). It spawns in all biomes (except the nether) including tundra, but will die soon after terrain generation there due to it being next to ice rather than water.
Once you have found some, farming is extremely efficient and it's quite easy to create as much as you want. If you really can't find any at all, you can always hack some into your inventory with InvEdit, or similar tools.