Selling my old phone

I'm about to sell my old Android phone and I want to make sure none of my stuff is still on it. I've got photos, work email, and a bunch of saved passwords on there. I know there's a factory reset in the settings, but I don't know if that really deletes everything or just hides it.

I think I should sign out of my Google account first, and maybe turn off the screen lock, but I'm not sure about the order. Also there's an encrypt option somewhere and I don't know if that matters. After the reset, how do I know the data is actually gone? Is there a way to check, or do I just trust the phone?

Personally I've never sold a phone, I tend to keep mine until they die... But I would think a full reset would be plenty.