This is JPA, not Hibernate specifically. The fact that you have a standardized API on top here makes it easier to find answers if you search in the context of the API, not the implementation.
The way to do it (as far as I remember, I don't use many to many relationships that often) is to remove the related entities from each other's collection mapping fields. So if you have EntityA and EntityB, you remove EntityA from EntityB and EntityB from EntityA. The persistence provider should then be triggered to remove the record from the join table.
Native queries should only be a last resort IMO.