Previously registered in UK

Where a vehicle was originally registered in the UK and the registration number is known it may be possible to re-register it with the original number. It may be worth trying the following link to check if there is a record of the vehicle. http://www.vehiclelicence.gov.uk/EvlPortalApp/
click on Vehicle Enquiry tab.
If it is not found there it may be possible that the original licensing office may still have the old registration details on record, but many have destroyed these since switching to computerised records.
Next gather any documents which relate to the vehicle, such as an old logbook, MOT certificates, tax discs or sale documents, that can be produced to prove the number belongs to the vehicle and obtain form V765. A dating certificate may also be required. 

Unregistered in UK or no trace of original reg.

In the case of a vehicle with no previous record of registration such as a "barn-find" or imported vehicle (imported vehicle is one purchased from outside the EU.) the following will be required:
Dating certificate, Insurance certificate, MOT certificate and form V55/5
Additionally one or more of the following may be required:
Nova certificate, VAT form 414, Customs form 

NOVA Certificate. From April  2013 a NOVA certificate from HRMC is required before the DVLA will register a vehicle.
As with any new regulation there is bound to be confusion and possibly variations on how local offices deal with them. 
For vehicles originally sold in the UK and kept in the UK, even if manufactured outside of the UK a certificate should not be required. If the DVLA office refuses then a call to Central DVLA should be made. 
For vehicles imported from the EU or counties outside the EU a NOVA certificate must be applied for. What may be difficult is supplying details of the importer or dealer who may have paid Customs duty on the vehicle. A certificate may not be needed for a vehicle over 25 years old, although this appears to vary between offices.
See the following for more information; http://www.hmrc.gov.uk/vat/sectors/consumers/personal-vehicles.htm 

Customs form   686   For vehicles imported before April 2013 it may not be required to apply for a Nova certificate if stamped and dated Customs form is available. This must bear a date stamp prior to April 2013, without a date stamp a Nova certificate will need to be applied for.

VAT Form 414. This may be asked for by the DVLA but there seems to be very little that can be filled in and for a vehicle from within the EC and Customs and Excise are unlikely to be interested. For vehicles from outside the EC a different form or proof that import duty has been paid will be required.
Dating certificate. These are normally available from owners clubs who have access to production records giving the year of manufacture for  the frame/chassis numbers. Since the introduction of the NOVA system verification of date may be be required from the manufacturer if still in existence. Production of the original logbook from the country of origin may be accepted as an alternative.  Without this a "Q" plate may be issued instead of an age-related number. Normally a rubbing of the frame number is required by those issuing the certificate, where the number has been tampered with or even ground out this may not be possible and other means of determining the number found. Where a number has be ground away the Police Vehicle Forensic Squad have been known to assist in finding the number.
Insurance certificate. It should be possible to insure the vehicle on the frame number but because of the National Database many insurers will only provide cover for 7 or 14 days without a registration number.
MOT Certificate. This is also done on the frame number and if insured the vehicle may be driven to and from the testers as long as it is booked in and local.
Form V55/5. Only available from DVLA local offices (V55/4 for new vehicles)

1. Registration mark - leave blank
2. Taxation class - Historic
3. Licence period - 6 or 12 months
4. Fee - check with DVLA for latest fees or leave blank if in person
5. Make - the DVLA is now insisting that the name used in the
     country of origin be entered (i.e.. Lambretta in Italy SIL in India)
6. Model - model name used in country of origin as in 5
7. Type of body - motorcycle etc.
8. Wheelplan - 2 wheel for m/c 2 axle for car/van
9. Colours - main and secondary or multi
10. Type approval No. - Exempt*
11- 15. - leave blank
16. Number of seats - (although the notes say not required for m/c - 2)
17 - 24. - leave blank*
25. Date of original registration - may not be known but enter as on MOT
26. Date of Registration in UK - date V55/5 handed in
27. - leave blank 
top right - If imported - Italy etc. (only likely to pose a problem if outside EC in which case leave blank and try claiming it to be a "barn find".
28. Date from which licence is to run - date submitted or 1st of month
29. Type of fuel - petrol etc
30. VIN/Chassis/Frame No. - as stamped on frame or plate†
31. Engine No. - as stamped on engine†
32. Cylinder capacity - 148cc etc
33 - 41. leave blank*
42. Year of manufacture - as on dating certificate
43. Name and Address of vehicle keeper - as will appear on V5
44. Date of birth - of keeper
45. Is the vehicle exempt from type approval - yes - over 10 years old*
46 - 49 - leave blank (unless of course it is a goods vehicle over 3,500kg) 
50 - Mileage - if speedo in kilometres convert to miles
Declaration - tick: duty payable
                            valid certificate of insurance 
                            Customs form (if imported)
                            MOT certificate
                    sign and date.

* If the vehicle is less than 10 years old then the type approval No. will be required and the sections 17 - 24 and 33 - 41 will need to be filled in. This information should be available from the manufacturer.

†With the Lambretta only the 6 figure part of the numbers were required.