Eggs are very hard to get right on a non-teflon pan, but do-able. First, you need oil or butter. I don't care what the infomercials say, I've never been able to fry eggs on a metal pan without oil.
Second you need to get the heat right. Oil forms a barrier between the pan and the egg, and also conducts heat better, what actually keeps an egg from sticking is the steam produced by the egg cooking. If the pan is too cold, or the transfer of heat to the egg is not fast enough then steam will not be produced quickly enough to keep the egg from sticking. You need to get the heat up on your pan. If the egg burns before it's cooked you've gone too far.