I've done a lot of research on websites but I'm not sure where to go from here. I assume the next step is to contact the organizations the kept the records (churches, government/municipality, etc.) but I'm not sure how to find the right place to contact and I'm not sure how or what to ask. I don't think its as simple as "Do you have a birth certification for John Smith", or is it?
Websites that have been searched:
Ancestry.com
familysearch.org
geneanet.org
The LDS church has tasked themselves with the burden of filming (and evenutally indexing and making available on the web) every public accessible record with genealogical importance still available in the world. Their collection of microfilms is staggering in its scope and growing continuously. What you find available at the Family Search website is just the tip of the iceberg of what's available on microfilm.
The catalog of their microfilm collection is available on-line. Once you locate a microfilm that may have information of interest to you, you can go to the nearest LDS church and fill out a request, and within days that microfilm will be available. You do have to use the microfilm at the LDS location, where there are research rooms set aside with computers, microfilm readers and usually items of local genealogical interest. There is a small charge to get the microfilm, but no charge to use it, and there is no requirement to be a member of the LDS to use this service.
Using this approach you can "virtually" visit court houses and town halls and state and national archives in many jurisdictions around the world. It is the eventual goal of the LDS to get all this information fully indexed and available on-line, but this is a never ending, monumental task. Until then the next best thing is scrolling through microfilms. This is getting to be a lost art, but one that can still prove serendipitous.
Genealogy and Family History was around way before the web was.
Go to your library and read some introductory books on genealogy. They will tell you how to do research and where you can look.
The number one place before you go anywhere else, though, are your oldest relatives. They'll have information that you won't get anywhere else which can provide you with places, family members, pictures and stories that you'd never have discovered otherwise.
Records and websites can wait. Talk to your oldest relatives first, before they forget and before they pass on.
There's no single answer to this question, so here are some additional suggestions beyond what's already been posted:
Google. Too many people don't make enough use of Google. Want to know how to get New York vital records? Search for "New York vital records" and you'll get a ton of hits. Same thing for any other state/province/country/etc. Try the same for other types of records too.
Online forums. There are many genealogy mailing lists and discussion forums, where you can ask specific questions and get help from experienced researchers. For example, Ancestry.com, RootsWeb, Genforum, JewishGen all have mailing lists or forums. Of course, we also have this great StackExchange site now!
Genealogy link compendiums. These provide a categorized database of genealogy-related websites. Some websites have actual records, other websites contain information about how to obtain records. Cyndi's List is a very popular one. Linkpendium is another.
Online tutorials. Some websites have online tutorials or guides to doing genealogy research. For example, FamilySearch's Learn site and JewishGen's InfoFiles.
Webinars. These are online presentations that are available on all sorts of genealogy topics. See the GeneaWebinars website for upcoming topics and schedules.
The value of a genealogical society cannot be overstated. Often, discussions with others who have been researching family lines (possibly for decades longer than you) leads you to avenues that you hadn't even considered. The society can often guide you to resources that they only share with members. They may have materials that can only be accessed when you physically walk through their door. They may even have sub-groups that specialize in the areas that you are looking for. So my suggestion for your next steps would be:
I would like to reinforce @CanadianGirlScout 's answer: talking to others doing genealogical research is invaluable in one's growth as a genealogical researcher. You can find such people at local genealogical societies, at regional or national conventions (which can be an eye-opener), and at local LDS family history centers. I've done all three, and learn something every time I do it.
Sometimes you have a targeted question that you can get help on, and sometimes it's just a small, causal remark that can open a whole line of research. Sometimes, it's just the act of explaining your question to someone that makes you reflect on what you had and had not tried.
Online groups are another excellent source of ideas on where and how to look for information after the obvious sources have been exhausted. These groups vary by area, ethnic or cultural identity, etc. Two obvious ones that come to mind are jewishgen and the Italian Genealogical Society; there are obviously many others.
In addition to the other suggestions:
