Map what you like, map what would be useful to yourself. Plan your journey, look whats missing on the map, possibly look at the aerial imagery to spot features which may be cycle-able ways and ride to explore and survey them. Knowing what to look for in advance makes it easier. And you get to know new areas!
It may be as simple as to survey the [`tracktype`](//wiki.openstreetmap.org/wiki/Key:tracktype)s (if `highway=track`) and/or [`surface`](//wiki.openstreetmap.org/wiki/Key:surface) or [`smoothness`](//wiki.openstreetmap.org/wiki/Key:smoothness) (at least if you go to ride out of a city). If you want to take notes while you ride you may want to use your own personal codes to take notes with a handy device. I often use a "real" GPS device and just create waypoints while riding and keeping details in my memory. E.g. you may set two waypoints shortly after another to make a record that a track is tracktype 2. grade2. Three waypoints for tracktype 3 grade3 and so on. With an easy to use Android app and a smartphone holder that should be possible too. I do not know OSMTracker that good. It is important that you are not distracted too much from riding, so only some presses of a big button is possible - rather no typing!
Similar to tracktypes you could have a look at some [quality assurance](//wiki.openstreetmap.org/wiki/Quality_assurance) error detection tool (I use keepright) to find nearby *potential* errors. Then you could go out with your bike and have a look at the place. Important: all those are just hints for potential errors. The tools may be wrong. This is special important to know if you are just new to OSM. Be sure to understand what the "error" is, before you attempt to correct it.
Similarly you may want to look at nearby [notes](//wiki.openstreetmap.org/wiki/Notes) and have a look if you can help by surveying.
If you make a break at some points you may take more notes at a saved waypoint.
Yes, also the mere GPS track recording and possibly uploading into the OSM GPS tracks database will help. It would be good to check your GPS track before you upload it. Is the quality okay or is it much more jagged/off than other already uploaded tracks?
I cannot comment on pen and paper - never used it in any surveying.
Also have a look at https://wiki.openstreetmap.org/wiki/Mapping_techniques .
Last, but not least: have fun and start slow! With a bit more experience you will get to know what to look for, what to map, how to map.