Traveling with a criminal history
This article is a travel topic
There is not very much information available on traveling with a criminal history, for reasons unknown. However for many countries the information can be found on the relevant country's immigration agency website, or by searching relevant laws. Many countries does not welcome criminals for obvious reason, however the amount of criminal history it takes to be refused entry into a country (or how long since your last convictions) varies from country to country. For some countries, particularly North America, even a minor criminal conviction 50 years ago can cause you to be refused entry, while others would require a conviction for a violent or serious crime to be refused entry. This page also lists ways (if known) to beat an entry bar due to criminal history.
In general it is very difficult if not impossible to travel to any country if you have a violent or repeated criminal conviction in the past, or if the conviction is very recent. In fact it is likely your own country may prohibit you from leaving your country if you have serious criminal histories, however in general they are not concerned about petty offenses. If you are on probation or parole you must follow the travel policies set by your probation officer to the letter, leaving the country (or even your county) without permission will result in a violation. Generally offenses committed in the destination country counts more than offenses committed outside of their country.
If you are asked about your criminal convictions, you must (and generally should) answer truthfully. Any false statements could result in a lengthy or permanent bar to that country, particularly the USA or Canada. Other countries like the UK and its former colonies have a concept of "spent" convictions that does not have to be declared once the condition for "spent convictions" are met, and that's about the only time one can get away with not answering truthfully.
The United States of America is generally very strict with criminal records, no matter how minor or how long ago it has been. They do not have any concept of "spent" or "pardoned" convictions, meaning you must truthfully answer any questions about criminal convictions even if your convictions have been spent or pardoned in your country. For citizens of any country who are eligible for the Visa Wavier Program, being convicted of any crimes, having unadjudicated arrests, or even a previously refused visa makes you ineligible for the visa wavier program!
There are numerous crimes that makes you ineligible to enter the US, and that includes "crimes involving moral turpitude", among other things. There is only a loose definition of "crimes involving moral turpitude" and the actual offenses are ever changing. Some of them may be minor such as shoplifting, while others can be very serious such as murder. The actual penalty of the conviction does not matter. If you are convicted of a crime involving moral turpitude, then you are ineligible to enter the US and little relief exists for this. Strangely, an exception to this is "purely political offenses." Again, this is also a very loose definition that the immigration officer can interpret anyway he wants. Being convicted of an "aggravated felony" is even worse, though just like crimes involving moral turpitude, these also have a very loose definition, therefore the offenses can change over time. However, there is absolutely no relief, and anyone deported or excluded for this reason cannot ever enter the US.
Do not even attempt to enter the US if you have been previously deported without a proper visa! Doing so is a felony (and a serious felony at that) under US law, and is punishable by up to than 20 years in prison. Do not lie about your convictions when questioned, as chances are they will find out. The US conducts extensive security checks on all visa applicants.
While Canada's policies on criminal record is strict, any convictions no matter how minor or how long ago makes anyone inadmissible, it is possible to overcome the inadmissibility by submitting an application for "rehabilitation". This process can take a long time and requires numerous references to prove that you are in fact rehabilitated and that further offenses are unlikely. If you do not want to wait that long and must go to Canada you may be able to apply for a temporary resident permit, however the reason must be justified and vacations are not considered a justified reason.
United Kingdom has a concept of "spent" conviction and immigration officers wishing to exclude or remove someone on the basis of criminal conviction must prove that the offense is not spent and therefore the person is not rehabilitated. A conviction is "spent" if more than 10 years has passed since imprisonment (if any) between 6 and 30 months. Any imprisonment over 30 month cannot ever be spent and therefore will always count against you. Imprisonment of less than 6 months or fines have an even shorter rehabilitation period (around 5 years or less).
The immigration wishing to deport you, or refuse entry on the basis of criminal conviction must prove that your convictions have not been "spent". The burden of proof is on them, not you so if you were refused entry due to a criminal conviction chances are your offense is not spent. If the offense is spent, then you don't even have to tell them about it and they cannot use it against you even if they do know. For consecutive prison sentences the rehabilitation period would begin at the time you were last in prison, unless the sentence is over 30 months.
Your visa wavier (if available) should not be affected by a spent conviction.
 European Union
The rules for the EU, specifically the Schengen Area, regarding character concerns is relatively lax. Questions about criminal convictions are not asked when applying for a Schengen visitor/business visas, and border agent and landing cards (there isn't any) doesn't ask this either. If any officials or forms ask you if you have a criminal history, you still have to answer truthfully, but in general if its not more than 3 years of imprisonment, or crimes involving alien smuggling or drug offenses that resulted in more than 2 years of imprisonment, then generally they will not refuse you entry or visa on that ground. Countries like Germany does have specific rules that states anyone convicted of an offense relating to public order with a sentence of more than 3 years, a drug offense with a sentence of more than 2 years, and any offense related to alien smuggling is deportable (a "must deportable). Like the UK they are more concerned with offenses committed in their country, rather than outside of the EU. Do not lie in any visa application or when answering questions to officials, because in Germany that is a "can deport". Not all countries have the same rule regarding character concern, so some EU countries may be more lax, however Germany is known to be a rather strict country so it is a good guideline on rules for the EU.
 Australia and New Zealand
These countries are rather strict regarding character concerns but Australia specifically says "in the last 10 years" so it is not known if convictions more than 10 years old are "spent". There are sporadic sources that suggests that these countries have a concept of "spent" criminal convictions and have rules in place that prohibits officials from obtaining information on spent convictions, but it is not known if it is automatic or it must be applied for like Canada. There are already other concerns that are just as strict such as being deported from any country (New Zealand), health concerns like being HIV positive or even having cancer or diabetes (one person has been refused a visa to New Zealand just for being obese!), that can result in visa being denied, refused entry, or even deported.