NP-completeness of vertex cover
A related, but different problem is Independent Set: it asks for a set of $k$ vertices that hits each edge at most once (instead of at least once).

A simple reduction from 3-SAT to Independent Set is as follows:


For each clause, we take a clique on $3$ vertices (i.e., a triangle). Each vertex of this triangle corresponds to specific literal appearing in a clause. E.g., a clause $(x_1\vee \neg x_2 \vee x_3)$ would have vertices corresponding to literals $x_1,\neg x_2,x_3$.
Whenever two vertices correspond to conflicting literals, we make those vertices adjacent. E.g., all vertices corresponding to $x_1$ are made adjacent to all vertices corresponding to $\neg x_1$.


We now ask whether an independent set of size $m$ (the number of clauses) exists.

Note that since there is a partition of the graph into $m$ cliques (created in step 1), the size of a maximum independent set is at most $m$ (one vertex from each clique). If there is an independent set of size $m$, then there is a satisfying assignment: such an independent set much select exactly one vertex from each clique, and which vertex is selected tells us which variable is used to satisfy that clause. This gives a satisfying assignment because the edges added in step 2 ensure that no conflicting literals are selected. Conversely, it is easy to see how a satisfying assignment corresponds to an independent set of size $m$.

This reduction should give you a good idea of how to approach the case for Vertex Cover (but this will require some slight modifications).