I'm not sure how much you know about it, so I will provide you with all I know about how espionage works. Just skip the bits you're already familiar with.
Once trained, a spy doesn't cost anything, no matter what you do with him. The training, however, can be quite expensive. While the first spy is relatively cheap with 100 bc, the cost slowly increases with each spy trained. Periodically, the cost increase spikes, making all subsequent spies even more expensive. Having to replace a spy can therefore be pretty bad, if your economy is not up to snuff.
The amount of money you can use to train spies depends on three factors: 1. your total income, 2. your spending ratio for training spies, and 3. your Espionage ability (which allows you to spend more money than the spending ratio would permit). If you have tool-tips enabled, you can put your mouse-cursor over the Espionage Spending in the Espionage tab to get a breakdown of how the cost is calculated. One last important piece of advice: keep your eyes on how long it takes to finish the training. Money that isn't needed to finish the training gets wasted, because it doesn't get applied to the training for the next spy.
Spies have three main-purposes: 1. gathering intel, 2. disabling enemy buildings, and 3. nullifying enemy agents.
1. The gathering of intelligence is one of the stranger aspects, because a lot of the most important information is already available to you. For example, the Foreign Relations tab tells you how many ships (and what kind) the enemy has, how good his economy is, what he is researching (and how long it will take), how many planets he has (and how many of them are defended), and what form of government he has. If you talk to the enemy, you can learn how much money he has (if it is a positive value), the names of all of his planets, what starbases he has, more information about his ships, and what techs he has researched that you don't have (only if they can be traded). When you change the topic of the screen via the small arrow below it, you can also learn all researched techs you have in common with this race. If you click once on an enemy ship, you can get general information about it (what weapon and defense categories it uses, the amount of HP, Speed, Range, and Level). If you double-click on the ship, however, you will open the Starship Intelligence Report which contains pretty much all information you will need about this ship (which is pretty weird, because access to the ship-details screen requires Low Espionage-Level, yet the SIR is always available).
That isn't to say, that increasing the Espionage-level doesn't has its advantages. The main one is access to all information of the enemy's planets. Sure, you can get some of this information by clicking the Spy button on an enemy planet if you have an idle agent, but getting to High Espionage-level is superior for three reasons: 1. the amount of information you can get is the same as with one your own colonies, 2. you can take a look on all enemy planets, not just those you have found, and 3. you can't be blocked by a Counter-Espionage Center.
There are two ways to increase the Espionage-level: active and passive spying. Passive spying is the quickest and safest way. To do it, go to the Espionage-tab in the Financial Management Screen, select one of the races on the bottom, and click on Place. This will send one of your idle agents to spy on this race. The amount of agents you use determines the time it takes and the level of Espionage you can reach. For example, with one agent you can only reach Low level. With four agents, the maximum, you will reach Low Espionage much faster and eventually reach the highest level. Once you've reached the highest Espionage-level (I always forget the name), you can reassign your agents, because there is no purpose in continuing the espionage. You won't get more info. Another advantage of gathering intel this way, is that the other race can't do anything to prevent it. The only way to lose passive spies is when the other race gets destroyed.
Gathering intel by active spying is a by-product of disabling enemy buildings. It is much slower than passive spying and contains the risk of losing the spy. Also, those spies can be blocked by a Counter-Espionage Center, and you need to know the location of a planet of the race you want to spy on. All of this makes active spying to gather intel a waste of time and money, so only use passive spies to do it.
2. Disabling enemy buildings is a nice way to indirectly harm your enemy. Slowing down research and/or production, reducing planetary approval, and lowering tax-income are some of the things you can do with it, depending on the improvements on the planet. To do it, you need an idle agent and know the location of an enemy planet. Go to the planet and either click on the red agent symbol on the lower left-hand side of the screen and then the planet, or simply click on the planet and then on the Spy button. This will open the Place/Remove Agent screen, which provides you a small amount of information about this planet. Most importantly, what improvements are build on it. To disable one of the buildings, simply select it and then click on Place Agent. Please take note, that not all improvements can be disabled.
You can change the selected planet by clicking on the small arrows to the left and right of the planet name. This allows you to go through the list of planets you have found of this race. However, you will not be able to select planets with a Counter-Espionage Center. The CEC automatically blocks any and all spying attempts.
Active spying has two bonus purposes: 1. slowly gathering intelligence (as mentioned before), and 2. a small chance to steal technology. Stealing technology is random, and depends on what techs the enemy has researched, and if those techs can be stolen. However, I wouldn't count on getting techs this way. You have better chances by simply invading an enemy planet.
3. Nullifying enemy agents is the last purpose for spies (and a big waste of money, in my opinion). If you have an enemy agent on one of your planets, you will get a notification. You can then click on the icon of this notification to bring up the Place/Remove Agent screen for his planet, allowing you to remove the enemy spy, if you have an idle agent. Another way to do this, is to go to the Espionage-tab in the Financial Management screen. Here you can see all active enemy agents at once, and remove them by simply double-clicking on them (as long as you have enough idle agents). Removing enemy agents, however, costs you one of your agents. Constantly replacing your agents is quite costly in the long, so it is better to prevent enemy spies from coming to your planets in the first place. To do this, build the aforementioned Counter-Espionage Center on your colonies. The CEC is pretty expensive to build and takes up one tile, so only build on your main worlds to start with. As time passes you can build it on your other planets, too, but with any luck this won't be necessary. Please take note, that the Drengin and Korath don't have access to the CEC in the un-modded game.
Well, that is all I can think of for now. I may have missed some small bits of information, but I hope it answers your, and anyone else's, question regarding espionage.
Edit: Sorry, for the wall of text. Did I write that!? 
