Since you have indicated in a comment to another answer that you are Polish, this answer does not cover the case of a British citizen wanting to move to the UK with a non-EU/EEA family member. The rules are somewhat different in that case. This answer applies to citizens of any EU or EEA country, and to citizens of Switzerland; it outlines the process for bringing a family member to live with you in the United Kingdom under the EU right of freedom of movement.
I will also assume that the narrow grounds for excluding EU nationals do not apply to you or your wife. That is, I assume that neither of you could represent a threat to public health, safety, or policy.
You want to bring your spouse to live with you in the United Kingdom. The first step is to get her into the country. You have not indicated her nationality, which is significant. Depending on her nationality, she will fall into one of two groups:
- People who need a visa to enter the United Kingdom (for example, citzens of India)
- People who do not need visas to enter the United Kingdom (for example, citizens of the United States)
If she falls into the second category, you can ignore everything to do with EEA Family Permits. Instead, you can just travel to the United Kingdom along with evidence to show that she is your wife, and apply for entry.
If she falls into the first category, she will need a visa to travel to the UK. In this case, you will need to present the evidence of your marriage as part of your application for an EEA Family Permit. This is free of chaarge, and should be issued on the basis of an "expedited procedure." (My mother in law received one of these last spring, as the dependent parent of my wife; if I recall correctly, it took a week or two.)
You ask how soon you can apply for the EEA Family Permit. According to the eligibility page, you can apply up to six months before you intend to travel to the UK.
(The eligibility page also mentions that the EU family member needs to be a "qualified person" or a permanent resident if he or she has been in the UK for more than three months. Since you are not yet in the UK, this does not apply to you. The only criterion you need to meet is that of being an EU citizen.)
Once you have entered the UK, your wife will most likely want to apply for a UK Residence Card. She doesn't require the card unless she wants to work, but she can use it to enter the UK after the EEA Family Permit expires (or if she did not require one in the first place), and it will serve as proof of her status in the country. The cost is £65.
Before she can apply for the residence card, you must become a "qualified person." This means that you fall into one of the EU freedom-of-movement categories: you're employed, self-employed, self-sufficient, or studying, or you qualify as a job seeker under EU rules. The details of how to prove this are covered in the uk.gov pages.
The residence card is also helpful because it will help your wife qualify for a right of permanent residence. You and your wife gain this right after living in the UK for five years, and your wife's right of permanent residence is independent of yours. Details of permanent resident status are also noted in the uk.gov pages.
Searching online, one can find stories of people whose EEA Family Permit applications were denied on the grounds that there marriage was, or was suspected to be, a marriage of convenience. The burden of proof in these cases rests with the ECO, so you should not at first concern yourself with proving your marriage to be genuine, unless perhaps your wedding was very recent. If this might be a concern for you, you can have a look at my answer to this question about a rejected EEA Family Permit application.