My intuition tells me that if $A \in H_2(M;\mathbf Z)$, then $A$ can be represented by a map $\Sigma \to M$, where $\Sigma$ is a closed (= compact boundaryless) surface, i.e., the connected sum of tori or of real projective planes. It would then seem that, in general, any $B \in H_k(M;\mathbf Z)$ can be represented by a map [closed $k$-manifold] $\to M$.
This is probably something really trivial but I'm not sure how to go about proving it "properly."
A representative of a homology class in $H_k(M;\mathbf Z)$ is a $k$-cycle, i.e., a formal linear combination ($\mathbf Z$ coefficients) of maps [$k$-simplex] $\to M$ such that the boundary is empty. So this can be viewed as a map [disjoint union of $k$-simplices] $\to M$ such that "the boundaries of the simplices get quotiented out." Thus, we can factor this map into [disjoint union of $k$-simplices] $\to$ [closed $k$-manifold] $\to M$, where the first map is just gluing the boundaries of the simplices together.
All this seems very hand-wavy to me and I'm not really convinced by my own pseudo-argument. Any help to make this more rigorous (or point out the fallacies!) would be appreciated.
This is a classical problem in algebraic topology, the Steenrod problem, which was more or less solved by Thom. Thom showed that this is true
Integrally for $k \ge 7$ there are counterexamples; the obstructions involve Steenrod operations for odd primes. (It's harder to glue a bunch of simplices into a manifold than you're making it sound!) See this MO question and this MO question for more details, as well as this overview of Thom's work by Sullivan.