Let $P$ be your polygon, $e$ an edge of $P$. I will interpret one aspect
of your question
as seeking all the maximal rectangles with one side flush with each $e$,
each rectangle $R$ maximal in the sense that
(a) $R \subset P$ but
(b) there is no other rectangle $R' \subset P$ with $R' \supset R$.
If you can solve this for one edge $e$, you can iterate over all $n$ edges of $P$.
Fix $e$ to be horizontal (by rotating $P$). Now your problem is to find the maximal
axis-aligned rectangles flush with $e$.
It is clear that $R$ is maximal only if all four sides of $R$ cannot be moved to enlarge
$R$. The edge $e$ determines one side, so there are three to be blocked by $P$ from
enlargement. A side of $R$ can be blocked by a vertex of $P$ lying in its interior,
or two sides can be blocked by their common corner resting on an edge of $P$. Various
possibilities are shown above.
A naive $O(n^3)$ algorithm can search through all possible blockers for the three sides,
yielding an $O(n^4)$ algorithm over all edges of $P$.
From among these, you could select, e.g., those with largest area, or largest perimeter, or whatever criterion is relevant to your application.
This naive algorithm can be considerably sped up. A series of papers led to
an $O(n \log^2 n)$ algorithm, which I think might still be the best available.
Whether it would be worth implementing all the tricks necessary to reach this low time complexity
is another question.
K. Daniels, V. Milenkovic, and D. Roth. Finding the largest area axis-parallel
rectangle in a polygon. Comput. Geom. Theory Appl., 7:125-148, 1997.
(CiteSeer link) Fig.1 shown above.
To address how to "continually cut [your] polygon down" requires some criterion to chose among
all the options. What I describe above is just a start,
identifying all the maximal rectangles.
I suspect any choice you make will lead to an NP-hard problem, and you'll be forced into
heuristics or approximation algorithms.
One heuristic is the greedy algorithm. Find, say, the largest-area maximal rectangle $R$ in $P$.
Create several new polygons by subtracting $R$: $P \setminus R$. Recurse on the pieces.
This would be easy to implement, and equally easy to thwart. :-)
Here is what I meant by thwarting the greedy algorithm:
Because no definition of what constitutes an optimal coverage by these rectangles has
been detailed, I cannot prove the greedy algorithm fails to achieve optimality.
But I am convinced that any reasonable definition of optimality will not always
be achieved by the greedy algorithm.