I have a custom object with OWD=Public Read Only. I have configured a criteria based sharing rule to extend Read/Write on the object to a public group. My user who is in the public group still cannot edit the records. Verified in the sharing table that the rule is granting edit to my user for the record she is trying to edit, however she cannot edit. What am I missing?
You simply have the permissions hierarchy inverted, which is easy to do given the complexity of Salesforce's security model.
The base of the pyramid is FLS and CRUD. Those permissions allow the user to interact with records of the object to which they have access. If a user has no Edit access in CRUD, they can't edit any records of the object.
The upper layer is ownership and sharing. If the OWD is Public Read Only, the user (who has Edit permission in CRUD) can edit only those records that they have Edit-level permission to, from the record-sharing layer. That means they own the record, they're above the owner in the role hierarchy, it's shared to them with edit rights, and so forth.
So: here, all you need to do is grant Edit permission - but not Modify All permission, which overrides the sharing layer and would allow the user to change all records regardless of sharing.