Magic Sites are present across the map from games start. Most sites are initially hidden, though there are some that are revealed as soon as a province is taken. Sites are revealed by using the "Search for Magic Sites" action of mages or through the use of remote site searching spells (e.g. Dark Knowledge).

Most sites provide their owner with gem income, though they can also provide recruit-able units/commanders, bonuses to ritual spells, spreading disease, and other effects on a province. Diligent site searching can greatly increase your gem income and let you break into magic paths that your nation may not have.

Other than their effects magic sites have a rarity, level, and set of terrains. The rarity controls how likely a site is to spawn, with rarity 0 being the most likely and rarity 2 being the least likely. The level determines how skilled a mage needs to be to find the site. The set of terrains controls where the site can spawn and if the site is unique. Mixed terrains appear to be able to spawn any site available to any of their individual terrain types.

Some site effects apply even before the site has been discovered. These include:

• Scale changes
• Disease spreading
• Horror marking
• Holy fire
• Holy power
• Random events relating to that site

The information below is taken from this analysis of magic sites. Please visit this guide if you are interested in the full numbers and a more detailed explanation than those below.

Ideally search with a level 3 mage everywhere (on land), though a level 2 is not much of a downgrade and it is likely not worth the turn to re-search a province that has already been searched by a level 2 mage.
Underwater a level 1 mage is sufficient.
Waste and Deep Sea have the best return, so it may be worth remote searching for F in deep sea if you can't get a mage down there easily.

Ideally search with a level 3 mage everywhere (on land), though a level 2 is not much of a downgrade and it is likely not worth the turn to re-search a province that has already been searched by a level 2 mage unless it is a cave.
It is barely worth searching sea provinces. If you do a level 1 search is sufficient

Ideally search with a level 2 mage underwater and in caves, though a level 1 mage doesn't miss much and it may not be worth going back over later.
Above ground a level 3 mage should be used as there are a significant number of gems in level 3 only sites (three rarity 0 ones are available for above ground provinces).

A level 3 mage is recommended for Caves and Deep Sea.
Elsewhere it is nice to have but level 2 also covers most things and it is likely not worth going back to search with a level 3 mage later.
Caves and Deep Sea have huge expected returns but are relatively rare. It is likely worth remote searching if you can't get a level 3 earth mage to your deep sea provinces.

The presence of the Unfound Door site (level 4, rarity 0) makes searching with a level 4 actually beneficial over a level 3, but the expected income difference is so low that I don't think remote searching is worth it unless you only have level 1s (and even then the return on Arcane Probing is very low as the example below shows).
Wastelands, Deep Sea, and Caves can't have this site so cap out at level 3 like the other gem types. Once again though level 2 searches are likely sufficient in these locations.

The well of pestilence site (level 3, rarity 0) makes a level 3 search for death worthwhile. As this site is usually easy to detect without searching (due to diesease and death scales) it is only worth searching to level 2 above ground unless you suspect a well.
Caves and seas are likely only worth searching at level 2 (no well), and for deep sea level 1 is sufficient.

It is worth searching to level 3 if possible but as always if you have searched to level 2 the extra level may not be worth the turns. Caves and seas cap out at level 2 and deep sea caps out at level 1.
Sea provinces can contain the Kelp Fortress site, which gives a free fort (level 1 rarity 0). You should search N1+ ASAP to save yourself on infrastructure costs if possible as an UW nation.
Forests and seas have significantly better gem returns than the other terrain types so you should search these first.

Not worth searching for gem income alone but you likely want to search to level 3 eventually if you are using blood for the chance of getting the summoning circle site (30% blood magic bonus).
The second gate at level 2 and first gate at level 1 also have a blood bonus but are unique, so are probably less likely to be in your territory in any given game despite having a lower rarity.
Obviously don't search for blood underwater.

Despite the presence of the Ancient Temple site holy searching gives a very low return. The underwater version gives 1S AND 1W so is definitely worth searching for religiously. Luckily most nations have priest mages or dirt cheap priests so the search is 'free'.
While H2 and H3 have some good sites (the records of mankind in particular) there are so few and almost all unique so finding them is very unlikely.

Each magic path contains at least one ritual spell for finding magic sites. Casting a remote site-searching spell on a friendly province reveals all sites of the targeted path, regardless of level. The spells are:

On the whole the return on investment of remote searching spells is very poor if you have consistent access to the path and are not concerned about turn economy. If you have multipath mages for that element then even the turn economy benefit is mostly lost.

For example remote searching astral as LA Pan (only S1 access) will give a return of 0.164 pearls per turn on average for a plains province (assuming two sites on average). This takes 19 turns to repay itself and is close to the best example for the standard remote searches.

Voice of Tiamat is potentially an exception here. If you haven't searched a province at all it has a return of 0.894 gems per turn/cast/site freq. in deep sea and 0.523 in normal seas. This gives a positive expected return in 5 and 8 turns respectively assuming 2 sites per province, though if you can already search for water and fire up to level 2 this decreases sharply. Being able to search for gems in paths you don't yet have access to is likely valuable beyond what the raw numbers would indicate though, so it may still be worthwhile depending on your circumstances.

Based on large numbers of experimental analysis, it has been possible to gain a rough understanding of how magic sites are generated on the map. Each province has a magic site frequency, which is the sum of the global site frequency (determined at game creation) and a terrain specific modifier. Generally (but not all the time), the most positive terrain modifier takes precedence in the case of provinces with multiple terrains.

Higher site frequency is associated with more magic sites: specifically, data has suggested that site generation may be modelled by 8 independent rolls for each of the site "slots", each with a probability of succeeding roughly equal to (global site frequency + terrain frequency modifier)/225. Additionally, sites have an assigned rarity, which is detailed in the inspector tool. Experimentally, the odds of each rarity site spawning following a successful roll are as follows:

Certain rarity 5 sites may spawn naturally. The odds of these spawning is currently unknown, but they do appear to be rather rare. These sites have unique independent pretenders which are always present guarding the site. The list of rare independent types lists these, along with other special independent spawns.

Additionally, some sites are flagged as unique, in which case the game can only place one of them.

A more comprehensive guide to Dom5 magic site generation by Loggy