The rear headrests can be raised only to a certain point. Pushing in the adjustment button on the driver side rail does not allow for them to be pulled completely out.
Turns out there is a pinhole on the passenger side rail/rod (see photo below).
Raise the headrest as high as it will go.
The headrest must then be lowered slightly until it clicks into the topmost groove. (This step is crucial)
Insert a paperclip like object into the passenger side pinhole and press in the button on the other rail.
While holding in both the pinhole and button, raise the headrest up to remove it.