This conflates several kinds of prefixes. I am not being thorough here; this is just a bit of clarification. There are basically four sorts that precede surnames:

• of or from a place
  examples are French, Spanish, and Portuguese de, Italian di, German von, Dutch van, etc. Some of these have spread, so you get Hungarian names with de or von. There is no living prefix of this kind in English, but a form of the word at occurs in Alan a-Dale and Thomas à Beckett.

  This may occur with the article 'the' in the place name, as in de La Rochefoucauld, Dutch van den...; and may combine with the article: Portuguese dos Santos, Italian del, della..., French, des, etc.
  
  

• son of or (rarely) daughter of
  Irish and Scottish mac, Welsh ab or ap, as in ap Rhys. In some common surnames the B or P has fused, as in Bowen, Pritchard, Price, Powell (from Howell).

  Irish also has Ó and its feminine counterpart Ní. These are used in living Irish: a woman called O'Brennan in English is called ní Bhraonain in Irish (Enya's surname). Actually, see Irish Gaelic family names by Ubiquity for a much better and more accurate explanation.

  Old French fitz (modern French fils).

  Arabic ibn or bin, Hebrew ben. There are corresponding female forms Arabic bint, Hebrew bat, but I'm not sure how commonly they are actually used.

  Arabic has an oddity in that when you become a parent you may be known as Abu... 'father of' or Umm... 'mother of'. I'm not aware of any other language (not even Hebrew) that does this.
  
  

• the expressing a quality
  French Leblanc = (the) White. Often fused with the name, as here. Italian La Guardia. But the same prefix may also be part of the place name in a toponymnic.

  Arabic al-Khwarizmi = the Khwarizmian, the person from Khwarizm. The L assimilates to certain consonants, but European transcriptions don't always show this: so you may see Anwar as-Sadat or Anwar al-Sadat, or plain Anwar Sadat). (And the al- is also seen as el-.)
  
  

• titles
  The Islamic title Hadji and the Christian Papa (priest) both occur in Greek names.

Such things also occur further afield. In Japanese no is used in some older names, though not modern ones; in Kenya we have (in which language I don't know) President Daniel arap Moi called President Moi, so arap is some such element.

A different matter is prefixes within place names, and people then taking their surname from that: as in Saint and all its forms (Hungarian Szent, Romanian Sfîntu, etc. etc.).

Prefixes are particularly common in Dutch surnames. Mostly they are placenames: Van der Graaff, Van de Graaf, or any other way to spell it, means 'from the ditch'; Van den Bos, Vandenbossche, etc. means 'from the bush' or 'from the woods'.

This is complicated by the fact that many manes of towns are toponyms as well; so Van Beek is likely to refer not just to any 'beek' (creek), but to a particular place known by that name, that may bear the official name of Hilvarenbeek, Vierlingsbeek, Spaubeek, Beek or any other Dutch town whose name ends in 'beek'.

What is also very common is a name that unambiguously refers to a town: Van Meurs, Van Arnhem, Van Gulik, Van Keulen.

This kind of name is particularly common on the south of the Netherlands, Belgium (Flanders), and was once used in adjacent parts of Germany. In Germany, however, this type of name became associated with nobility: any surname with 'von' (Von Lippe zu Biesterfeld) implied a title, so the prefix was dropped from common names in Germany, and the whole type of name disappeared.

There are many other prefixes in Dutch surnames: In 't Veld (in the field), 't Hart (the heart), De Bakker (the baker), Vennegoor of Hesselink ('Vennegoor' or 'Hesselink').

In the Netherlands, the spelling of prefixes in surnames varies with the name, but capitalization and interpunction doesn't, and when sorting names, prefixes are not considered. For example, Van der Beek and Van de Beek are two distinct names, but Vanderbeek is not used, and both names are sorted under the B, before Beekmans.

In Belgium, even spelling and interpunction vary with the name, and sorting considers prefixes; in Belgium, Vander Beek, Vanderbeek and Van der Beek are three different names, all sorted under the V.

Fortunately this isn't the node to discuss prefixes in place names (ranging from 's-Gravenhage to Sint-Job-in't-Goor).

Suffice it to say that some software companies specialize in identifying and sorting address data; their activities are entirely based on sorting out this particular problem for others.

The prefix af or (rarely) the more modern spelling av, is common for Swedish noble family names. The word litterally means "of" in this case. Examples: "af Ugglas". The German "von" is also common, e.g. "Carl von Linnaeus"

The only rule for these prefixes in Sweden is that only noble families can have them. An ordinary citizen can't pop an "af" or a "von" into his name because it would look good.

To make things complicated: the use of these prefixes is a relatively late invention. The old Swedish noble families often had short names, usually corresponding to a prominent design on the family coat of arms, e.g. "Grip" (Griffin) or "Bielke" (bar). Sometimes, though, noblemen added the name of their estate after the family name, using "af" or "till" as a preposition.