Don't count solely on soundex. While the soundex search option, when available, is a great way to pick up alternate spellings, it may not get them all. OWENS and OWEN, for example, are commonly seen variations of the same name - yet they have different soundex codes. Therefore, a search for OWENS will not pick up OWEN, and vice-versa.
Try a wildcard search. If you aren't sure how to spell a name, some census search engines allow you to use special symbols called wildcards to represent some unknown letter or letters in a word. Check with the specific census index for specific wildcard rules and symbols, but most (including Ancestry.com) allow you to use an * to represent an unknown number of characters at the end of a word (a search for john* might return john, johns, johnson, johnsen, johnathon, etc.) Usually you need to have at least three characters preceding the *. Another commonly used wildcard character is the ? which is often used to represent a single character within a word (a search for sm?th would match both smith and smyth). A search for "Harriet Sto*" in the 1860 U.S. census, for example, helps find Harriet Beecher Stowe living in Andover, MA, even though her last name was actually indexed as "Stone."
Familiarize yourself with nicknames. It's not uncommon to find families providing census takers with their formal birth names in one census, and then using the names their friends and family called them by in another. Mary might be listed as Polly, Alexander as Alex or Al, and Elizabeth as Betsy, Bessie, Beth or Eliza. Familiarize yourself with the names your families commonly used, as well as common nicknames for popular first names.
Check the middle names too. You probably wouldn't believe how many of my rural North Carolina ancestors listed all of their children by first name in the 1870 census and then by middle name in the 1880 census. Most people wouldn't even recognize them as the same family! As with nicknames, in many areas of the world it is common for an individual to be known to families and friends by his middle name. Be sure to search for middle names, baptismal names, and other alternate names.
Search by surname and location. When you're pretty sure you know where an ancestor was living but traditional searches just aren't turning him up, try searching by surname only - restricting by state, county, district, or town as necessary to bring the number of results down to a reasonable number for browsing. You may even discover previously unknown relatives!
Search for initials. When you can't narrow down the location enough to use surname only search, and you can't find them listed under their first name, check for initials. Sometimes those census enumerators were lazy! Initials may have been used for first name, middle name or both. M C Owens would come up under a search for either 'M Owens' or 'C Owens,' for example.
Search for siblings, children or other family members. When an every name index is available, don't forget about the rest of the family! Your ancestor's first name may have been hard to read, but her brother's may have been a bit easier.
Search for neigbors. If your ancestors have been living in the same place for a while, search for people who were listed nearby in neighboring census years. If you find a neighbor in the index, then head to his page and check a few pages on either side for your ancestor.
Leave out the name entirely. When all else fails, and the search engine offers enough other options, forego the name and search by other known facts. Searching for someone living in Wilson County, NC, in 1850 who was born in Virginia in 1789 will narrow down the field considerably. Sometimes this is the only way you'll find those people whose names were seriously mangled during the indexing process. Searching by first name only, along with other identifying information such as date and place of birth, can also turn up possibile matches for women who have married.