you can choose at any time you like, there are imperial recruiters in bestine, on tatooine, and rebel ones in anchorhead on tattooine, there are others too, on naboo etc, but those are probably the easiest to get to for the moment.
you will need to gain 200 faction points in whatever you want to join, do that by using the mission terminals, either rebel or imperial, reminds me, there is a imperial recruiter and a imp mission terminal in mos eisley, in the building where there are 2 imps outside, between the starport and shuttleport. the rebel mission terminal is inside the cantina - downstairs, in anchorhead.
hope that helps.