Here are some polyominoes:
The general definition of a polyomino allows for holes (I think). This question restricts itself to those polyominoes that are hole-free.
It would be nice if the algorithms were characterized by their $O(f(n))$ cost in time, where $n$ is the number of vertices in the polyomino.
Wikipedia page Polygon partition gives references for some relevant surveys, including one by Keil, J. M. (2000). Polygon Decomposition. Handbook of computational geometry, 2, 491-518. In particular, Section 3.1 "Partitioning orthogonal polygons" has references for multiple algorithms to partition a rectilinear/orthogonal polygon into minimum number of rectangles, both approximate and exact algorithms. Polyominoes can be considered as rectilinear polygons, so the algorithms should also work for polyominoes.
One of the referenced papers from the survey is "Minimum partitioning simple rectilinear polygons in O(n log log n) - time" by W. T. Liou, J. J. Tan, and R. C. Lee, published in 1989. The publication can be found in https://dl.acm.org/doi/10.1145/73833.73871.