how do simple SQLAlchemy relationships work?
Yes, you need user_id = Column(Integer, ForeignKey('users.id')) or user_id = Column(Integer, ForeignKey('users.id'), nullable=False) if it's mandatory. This is directly translated to FOREIGN KEY in underlying database schema, no magic.
The simple way to declare relationship is user = relationship(Users) in OpenID class. You may also use users = relationship('OpenID') in Users class. backref parameter allows you to declare both relationships with single declaration: it means to automatically install backward relationship in related class. I personally prefer using backref-s for self-referring relationships only. The reason is that I like self-documented code: when you look through it's definition you see all defined properties, while with backref you need to look through other classes (probably defined in other modules).