Since you intend to create a new object - any primitive would do to start a creation in edit mode - however first you have to have a base for a new object. Add a Plane - it has a least amount of vertices from all default objects.
In edit mode you can select all vertices and Alt-M merge them which leaves you with one vertex per object only. You can start to E extrude this (or just Ctrl mouse click in the desired location; if nothing is selected Ctrl-click would start a separate mesh island inside the same object).
To have newly added vertices ‘stick’ on some surface best option is to add a Shrinkwrap modifier to the newly created object and choose as a target object you want to ‘trace over’.
To make face creation even faster you could use addon Bsurfaces which allows to draw Grease Pencil strokes which in turn determine general direction and size of the face patch you want to create; after you click the button AddSurface (on the toolshelf, if the addon is activated) you guessed it - surface patch is added where you had drawn guide lines. You are left to adjust amount of faces you want there and check if Shrinkwrap has done proper job.