Wherever feasible, ccTLDs should be first preference. Google recognise them and try to target a site accordingly.
User preference should be considered too, as users in some countries exhibit strong preferences for sites on their own ccTLD. For example, a "survey conducted by AFNIC in June 2010 showed a marked preference among French people for .fr domain names" (AFNIC is a body that administers French TLDs).
According to Google, subdirectories and subdomains of a gTLD are treated equally for geographic targeting purposes, so either
fr.example.com has the same potential from an SEO standpoint. This applies beyond the realm of geotargeting, too. There's much mythology about differences between the two. Use whichever makes sense technically.
If using either subdomains or subdirectories, register each separately in Google Webmaster Tools and use the geographic target setting for each. You may wish to set this to "unlisted" for the root domain if that's intended to address a global audience, as this should help avoid any unwanted location signals arising from your server's location.
I've focussed on Google so far since they're dominant in the places you mention. Bing, unlike Google, still use code declarations for geographic targeting, so use of the
Content-Language meta element or the
lang attribute of the
<html> element can be used.
In either of those cases, if you're targeting a specific country as well as language, declare language/country pairs with valid ISO codes, e.g.
en-GB (English, UK) or
en-US (English, USA),
fr-FR (French, France) or
fr-CA (French, Canada), and so on. If just a language, that's fine too, e.g.,