It is well known that d-regular bipartite graphs have a perfect matching. Applying this iteratively, it even follows that such graphs can be decomposed into the union of d perfect matchings. (The existence of a matching follows from Hall's theorem, which is probably beaten into students during any combinatorics course.)
Find an Eulerian circuit of the graph in O(m) time, which exists for any even d. Now throw out the 2nd, 4th, 6th, etc edges of the circuit. You are left with a graph that is (d/2)-regular. Recurse to find a matching.Why do you get a regular graph when you throw out all edges on even positions? Think about it: the edges of the circuit go back and forth between the two parties of the graph. For any vertex v, its d incident edges are grouped into d/2 pairs of consecutive edges. One edge of such a pair appears on an odd position in the circuit, and one on an even position.