From Wiki

Attestation - This is done by a solicitor, one who is a Notary Public. This confirms that the Certificate is what it claims to be.

Legalisaton - This is done by the FCO. For the public, this is done either over the counter or by post at the MK office. Basically, an Apostille Certificate is attached to the back of the original certificate, authenticating the document.

Embassy legalisation - This is done by the relevant Embassy for the country in which you want to work, in this case, the UAE Embassy.This must be done last, as the two other previous steps need to be completed beforehand.

The process in a little more detail:

A solicitor must sign and stamp a copy of the degree to make an authentic copy.

This and the original are taken to the legalisation dep't of the Foreign and Commonwealth Office (FCO). The Legalisation Office is located behind Ashton House on Silbury Boulevardin in Milton Keynes. Its a ticket queuing system, very fast in the mornings and the actual legalisation of a document takes around 15 minutes. The fee for legalisation of each document is £28. At the public counter payment is accepted in cash or by credit/debit card.

Norfolk House (West) 437 Silbury Boulevard Milton Keynes MK9 2AH The public counter is normally open from 9.30am to 3.30pm Monday to Friday. No appointment is necessary.

Here is the link

You then take the original and copy to the UAE Embassy. This is opposite the Natural history museum, etcetera. It costs around £20.Three working days should normally be allowed before collection of documents lodged at the Embassy for legalisation. The Embassy now offers same day “Express Service” upon the payment of £10 per document.

48 Prince’s Gate, London, SW7 2QA. Tel. 020 78088306, Email : legalisation@uaeembassyuk.net Hours 09.30 – 13.00 Monday – Friday

Apparently, if you post your stuff to the FCO, and include a stamped addressed envelope, the FCO will do their bit and post it onto the relevant Embassy for you. Worth perhaps giving them a ring?

There is a FCO office in central London, but this tends to be for business users only and I think you have to pre-register with them but they can provide a same day service. The MK office charges £28 per document, whereas the London Office charge £71 !

Have a read of this thread which may help further.

If you are already in the UAE:

A simple way for degree certificates here:

British Council

The process being here: Attestation_procedure_british_council_dubai_-_updated.doc

After filling in this form:

[1]

The thread with the information is here with the info posted by BE member "Millhouse".