The topics of navigation and cartography are two sides of the same coin, and there are entire books written about each. It is interesting to study the history of cartography because it very graphically shows the corresponding improvements in navigation over time.
In order to make an accurate map, you need to know first where you are making your observations from. Making the observations from a previously known position will result in much greater accuracy. This position may have been established by an earlier survey (eg, working from a known point on an existing map) or by being able to independently figure out your position with good certainty on the position of the globe.
Prior to the mid-1700's, the primary means of navigation was dead reckoning (DR). This requires that you iteratively advance your position on the map from your last known position using direction and time/distance. Of course, over time, errors will compound resulting in reduced accuracy. You must have a way of measuring your direction of travel and a (somewhat) accurate value for your speed.
Later in the 1700's, it was possible to navigate more accurately using celestial navigation. This allowed a skilled navigator to determine his position rather accurately (typically within a few miles) at any point on the globe. The position was typically found once each day and advanced using DR as necessary.
Today, we have GPS.
Measuring distance north and south is considerably more easy than measuring distance east and west. Lines of latitude are evenly spaced, where lines of longitude are not. In the northern hemisphere, latitude can be measured by finding the elevation of Polaris above the horizon.
Conversely, lines of longitude converge at the poles resulting in variable distance. Measuring longitude is very tricky, though there is a great book called "Longitude" (Dava Sobel) which covers the topic (and its solution) exceptionally well.
You will note in many older maps, distances north and south are quite accurate where distances east and west are often distorted.
To your immediate concern - mapping a shoreline - I would recommend using a GPS receiver (modern equivalent of celestial navigation) to record your position at the moment you are making your observations. In making your observations, use a cruiser compass, which allows you to shoot relatively accurate bearings from your position. Record the bearings to several reference points over a couple of observations, and you will be able to triangulate them accurately on paper. From these triangulated points, you will have to interpolate the coastline between the points.
I did a lot of navigation in the Navy, and this technique is the converse of what is known as "piloting". With piloting, you are determining your location using bearings from reference points on accurate maps. Here, we are using the bearing to objects to determine position of points along the coastline. Still, it works much the same way.
Maps - especially of shorelines - were almost certainly made from observations taken from boats. Naval navigation is much more accurate than navigation on land (especially without good maps!).
You give a nod to the problem of dead reckoning in your question regarding the determination of speed. I don't kayak, but I do hike, and I have found that over time, things average out. I can't say what my hiking speed is at any instant, but I can say that I average about 2.8 miles per hour over the course of several hours.
If you are interested in this topic, I'd recommend you pick up a copy of Dutton's Navigation and Piloting. This is a text book used to teach navigators, and is perhaps the authority on the topic. The older versions (older than mid-1980s) are especially interesting since they still include some information on celestial navigation. My copy is from 1969.
I'd also recommend Barefoot Navigator (Jack Lagan) which covers the navigation skills of the "ancient" cultures.
"Finding Your Way Without Map and Compass" (Harold Gatty) is another fine book. The author was a navigator (both naval and aviator), so he has some interesting takes on navigation.
Finally, "Longitude" (Dava Sobel) is a fantastic read about solving the problem of longitude.