No matter what your situation is, there are some things that are pretty much universal about starting a new team, where there was no team before.

You will have to be an Ultimate frisbee fanatic.

The easiest way to get people interested in playing Ultimate (listening to what you have to say) is for you to come across as being extremely enthusiastic. Enthusiasm is infectious. People look up to someone who is enthusiastic about what they do, Ultimate is no different.

Be positive.

You will have to be positive in every aspect of recruiting, practicing, and teaching. Be sure to point out the good points in everyone's skills. Follow any improvement players make, and try to mention these improvements often.

Ultimate is as much a social outing as it is a physical fitness outing.

Always try and meet somewhere after practice on a regular basis. You will find that some people who can't always make Ultimate due to schedule conflicts, will often show up to the social outings afterwards as long as there is some regularity to the outings. You will find that once you have recruited people, the social aspect of the sport will keep people coming out to practice as much as the sport itself.

Get your team to participate in beginners or fun tournaments as early as possible.

Nothing motivates beginners like travelling to a tournament and playing an intense match against other people like them. Most new players come back from tournaments enlightened as to the true extent of the possibilities of being a member of the Ultimate community.

Be organised.

The more organized you are, the more comfortable people are and the more likely they are to join. Having a typewritten description of the game to hand out to potential players during recruitment or a phone list/contact sheet drawn up immediately and passed out to the members shows that you are organised and committed to your job as coach.