Torsten's answer was good, but there are also more elementary answers. Here's one, which is essentially a big transversality argument, followed by a mild de-singularization.

Let me consider $M$ to be a triangulated 4-manifold, and represent a class in $H_2(M)$ as a sum of 2-faces of the triangulation. For each 2-face appearing with multiplicity $n$ in the sum, take $n$ copies of the face, pushed off of each other slightly and meeting only at the edges.

Now, along each edge (1-face) of the triangulation, since we started with a 2-cycle the total number of triangles meeting there is $0$. (This is a signed count if we are working in $H_2(M; \mathbb{Z})$, and means that there are an even number if we are in $H_2(M; \mathbb{Z}/2)$.) Along each edge, pair up the incident triangles in an arbitrary way that's compatible with the orientations, and resolve the intersections along the interior of the edge according to that pairing. (A neighborhood of the edge looks like $D^3 \times I$; the incident triangles are coming in from fixed directions, i.e., at fixed points in $S^2 \times I$; so given any pairing of the points on $S^2$, we can just join them up and avoid the edge altogether. It's easier to think about what happens in a 3-manifold, where it's very similar, you just have to be more picky about how you pair the incident triangles.)

After the last step, we have a surface $S$ with codimension-2 singularities at points in $M$. For each such singularity, consider a small ball $B$ in $M$ and consider $S \cap \partial B$. This is a link $L$ in a 3-manifold (oriented or not, depending on which homology we look at). Replace $S \cap B$ with a Seifert surface for $L$, and we're done. (You could also use any surface with boundary $L$ inside the 4-ball $B$ instead of the Seifert surface, of course. Frequently you can get lower genus that way.)