There are a number of research methods you can use depending on your scenario.
But first, state your research goals...
Get the questions out of your head and onto paper and share them with others, get feedback. Start out getting all collaborative right off the bat. Plan the whole process and verify you actually have the time and funds available.
...and define how you will use personas
Ask first whether you actually need personas and if you think you do, then how you will use the personas. Ensure that personas don't just become an artifact, because the value is so not in the artifact itself.
Contextual inquiry - user interviews
*If you do have existing users*, interview them, but don't just take the path of least resistance and interview people you know or people in your building or friends and family. Interview people you don't know and from different locations or environments that reflect real world use.
Try and interview at least a dozen people as you won't be able to spot trends with fewer people - remember you're not trying to find the 'perfect user', you're trying to find a sense of commonality from different sources that you can project and overlay onto your persona. But as well as trends, you're also interested in surprises. Personas are meant to gloss over the irrelevant human idiosyncrasies, but things that 'make people human' are desirable factoids for personas. Ask the why. Lots.
But on the other hand, if you're not learning anything much new as you interview more people then you're wasting time. It might be useful to plot 'the total number of factoids' as you interview each person so that you can see when you reach a plateau.
*If you don't have existing users*, then you need to increase the number of other sources of information to account for this, but it's worth looking at using one or two other sources in addition to user interviews anyway.
Liken this to Damien Newmans squiggle of the design process where at the early stage of design, the more squiggly the squiggle (ie the more input/research), the straighter the 'solution line' that emerges.
In the case of no existing customers, you need to actively seek out people you would like to be your users. As well as going where the users are, go to locations where they might congregate. Don't just talk to people, but make sure you observe them too. Watch them go about their business in their own environment. Empathise with them. Become them. Record their language. Do this because you want to empathise with your personas to make them work, so don't be fooled into thinking that you can easily empathise with a persona 'on paper' if you haven't done so in real life.
People are happier to talk in their own environment and comfort zone, so going to their location works for you in several ways. With permission, take pictures or video so you remember their environment and objects around them. You're looking for a story around your persona - when you use your personas you're going to ask questions like, 'would Bob use this?' 'What would Bob the power user think of the way this looks', 'How would Bob find the experience of using this product', and without being able to empathise with Bob, and without positioning Bob in this contextual storyline, it's almost impossible to say what Bob might think.
If possible, try to review your findings against what you origianlly put on paper for your research goals so that you have a sense of understanding whether you achieving what you set out to do, and can adapt if necessary.
Where you can't get enough information from the above methods, or time or money is not available there's a kind of quicker 'Guerrilla user research' alternative using indirect information instead of first hand research. So this can include second hand research, informed hunches, outcomes of stakeholder interviews and brainstorming workshops based on domain knowledge and gut instincts about users and their motivations, made up but informed stories about what a day in the life of a user is like, before during and after using the product or service you will offer.
...but keep it real
Precisely because proto personas are 'second hand' research they need validating - or invalidating - against the real world if at all possible. The last thing you want to create is a bullshit persona that you can't actually backup with real information so validation of proto personas is really critical.
If the information is real, the greater the chance of the persona being taken seriously. And when those who control the purse strings start pushing their 'opinions' onto the project, you want to be able to point them at the persona and say, no 'Bob the power user wouldn't like that' and be able to back that up with the research behind it. If the persona ends up with fake content, and you use the personas as your design focus, you're whole direction is fundamentally flawed.
Don't forget the competition
Don't be afraid to go on the hunt for information about users of a competitor product - maybe visit physical locations or online places where these competitor users 'hang out'. If competitors don't exist or are information about them is difficult to locate, try and be a little inventive and think laterally about what else your users might typically do or places they go and where they might congregate.
Take the journey together
Above all, remember that creating personas should be a collaborative experience for everyone to be on board acoss muliple departments and at multiple levels in the company org chart. In the same way that customer journey mapping holds all it's value in the collaborative act of mapping, so is it the case that the value of the persona is not in the artifact itself but in the act of its creation and subsequently in the life of the persona who you must ensure stays alive and well at all costs. Don't farm out the persona creation completely to a third party unless they are going to come in and facilitate the research and persona development within your organisation, instead of without you.
By the time the personas actually materialize, all the stakeholders should already know them - intimately. [No - not that intimately, stop it!] Everyone will have been a part of the journey of persona research and know there's no fluff, no bs, and that nobody just made this stuff up.
References / Resources
Tina Calabria An introduction to personas and how to create them
Jeff Gothelf Using Proto-Personas for Executive Alignment
UIE Jared Spool Five Factors for Successful Persona Projects
UIE interview with Kim Goodwin
Jill Christ and Stephanie Carter Avoiding Bullshit Personas
Leah Buley's UX methodologies described in her workshop UX team of one bootcamp at UXLondon 2012