There are many ways to implement Machester decoding. The method used will depend heavily on the following factors:

1) The data rate. If the bit toggle rate is faster than say 1/10 the instruction cycle rate of your microcontroller then I think you need to look seriously at a hardware solution.

2) Is the data rate widely variable? If there is rate dither and variation in the data that is greater than some amount (I cant guess this amount for your system) then it may be necessary to use a PLL to generate a recovery clock which is 2X the data rate. This clock can then be used to strobe in the data at 1/4 or 3/4 of the position in each bit cell.

3) Is the received waveform free from more than an occasional glitch or false transition? Normally these problems are caused by noise in the transmission that goes over the detection threshold in the receiver circuit.

Here are a couple of interesting links to places on the web where you can look at some decoder ideas:

http://www.hitex.demon.co.uk/8051/manchester.html

http://www.atmel.com/dyn/resources/prod_documents/doc2817.pdf

http://www.xilinx.com/xcell/xl17/xl17-30.pdf

Hope this info is helpful.
Michael Karas