How fundamental are matroids and greedoids in algorithm design?
It's difficult to answer the question "how often". But as with all "underlying structures" the benefit comes from recognizing that the underlying problem one is trying to solve has a matroid (or greedoid) structure. It's not just matroid problems. The matroid intersection problem has a specific model (bipartite matching).

Nick Harvey did his Ph.D thesis fairly recently on algorithms for matroid problems and also looked at submodular function optimization (which generalizes matroid problems). Reading the introduction and background to the thesis might be helpful.