A servo will cause two main forms of interference. One is the spikes accompanying any DC motor that uses brushes, the other is the drop in voltage as the motor loads the supply. The former is relatively easy to suppress using small capacitors around the motor, and sometimes RF chokes for high frequency stuff.
The latter is a little more difficult to deal with. Any power supply (voltage source) will have a characteristic internal resistance. This forms a potential divider with your load and the voltage measured from the PSU output is the voltage measured at the centre of this divider. Internal resistance will be a couple of ohms or less, depending on the supply. This is why the terminal voltage drops a little when you apply a load.
A DC motor at startup is drawing much more current than when it is running at normal speed. Servos have lots of startups. A hefty electrolytic capacitor near the motor will take the load briefly during this short period and reduce the drop caused on the PSU voltage.
In general, the easiest solution, aside from using separate supplies, is to make sure the supplies internal resistance is low enough so that the expected loads will not cause a significant voltage drop. As a rule of thumb, mains powered PSUs with a higher current rating will have a lower internal resistance. Although your servo might just draw 500mA, I would recommend at least a 1A or 2A supply. The greater the overhead, the lower the voltage drop will be and the less it will effect your microcontroller.
Generally, re-chargeable batteries have a lower internal resistance than other types. I have had reasonable results using this method: Power the PICAXE from 4 rechargeable AA NI-MH batteries (4.8v) using a series rectifier diode which drops the voltage to around 4v. Power the servo directly from the battery. Use electrolytic capacitors near the PICAXE to smooth the supply and maintain the voltage when the motor causes drops in the battery voltage (during which the diode stops conducting and may even become reverse biased)
Remember though, the PICAXE ADC uses its supply voltage as a reference so any variation (due to batteries running low or whatever) will effect the reading. For accuracy in this respect, a 5v regulator, such as the old 7805, is essential.