In my opinion, the sooner the better. But before you schedule for your first test, make sure you see through the test structure and topics to assess yourself about the appropriate duration of preparing for the test. Make sure you have at least 30 - 45 days before the test (some would say 2 months). It would also depend on how much time you have (also if you are simultaneously working) to channel to GRE prep.
About the number of times to take the GRE, it all depends on your satisfaction and ofc the competitiveness of your admission department. As for me, I sat twice. The first time (back in July) was much of a 'trial' you know. It was quite nerve-racking (it's the first time!), all my friends said "It's difficult!!!", plus I really didn't know much about the 'real' difficulty of GRE (compared to preparation materials I used). But for the second time (in Oct) things got much much better- I was not at all nervous for the second time, I knew what to expect and what are my weaknesses to work on.
Good luck on your prep!!