you can also try
www.anibis.ch and
www.comparis.ch as general seach sites; anibis is in French only and you can either select "immoblier" or in the rechercher option, you can type in the town you want to live in - bear in mind though that this site also does buying and selling, so unless you are specific, you will get a broad search. Comparis is in english and pretty much brings together homegate, immostreet and other seach sites.
My partner and I found our apartment through anibis after three months of searching (although the apartment was later advertised on homegate). We were quite specific in terms of what we wanted though, but other friends have got theirs in less time than this. You need to be quick.. when you see something advertised, ring up immediately, otherwise you risk losing out.
We also registered with an agency, but they did diddly squat for us.
Make sure that you have all the necessary paperwork for the agency; ie letter re employment/contract, permit/letter from canton issuing permit, letter from the office de poursuites may be required; each agency may ask for slightly different things. we missed out on one great apartment because we were a day late in returning a copy of a document!
Good luck