Т.к. делал это неоднократно, посоветую следующее.
На одной (!) странице (обычный белый лист) нужно ответить на три группы вопросов:
1. Когда, где и кем работал? Т.е. идентифицировать когда и в каком качестве дающий работал с рекомендуемым.
2. Чем занимался? Какие были достижения?
3. Краткая характеристика как человека (или сотрудника, или исполнителя, или коллеги, или руководителя - в зависимости от того, кто дает рекомендацию). Плюс хорошее пожелание от дающего.
Разумеется, нужно указание данных и координат давателя и его собственноручная подпись. Бумажку можно потом отксерить и раздавать вместе с резюме.
P.S. А вообще всё это (и рекомендации, и примеры) есть на работных сайтах.