Travelling with a 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 is eligible for the Visa Wavier Program, being convicted of any crimes, having any arrest, or even a 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 are only a loose definition of "crimes involving moral turpitude" and the actual offenses are ever changing. Some of them may be minor like shoplifting, while others can be serious like 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 few relief exists for this. Strangely an exception to this is "purely political offense", 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, and like crimes involving moral turpitude, has very loose definition and therefore the offenses can change. Unlike crimes involving moral turpitude, there are absolutely no relief from this and anyone deported or excluded for this reason cannot enter the US forever.
Do not even attempt to enter the US if you have been previously deported before without a proper visa! Doing so is a felony (and a serious felony at that) under US laws and is punishable by no more than 20 years in prison. Do not lie about your convictions when questioned, because chances are they will find out as 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.
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.