How do certain apps record everything we type in android? Certain apps like Type Machine claim to be able to record everything you type. You have to install it and activate it from the device's accessibility settings, then it can somehow record typed text.

How is this even possible? It is not a keyboard app , so it is not directly accessing the keystroke information. Also, according to the android documentation "Only the system is allowed to directly access an IME's InputMethod interface" and 'Only the active client's InputConnection will accept operations'. 

Given that a 3rd party service like Type machine is neither a  system app or the active client, how  is it able to record typed information?
It installs an Accessibility Service. These services are usually used as screen readers (like TalkBack), and thus have access to on-screen text. It is thus able to record on-screen information. If you install the app, you'll notice it prompts you to register it as an accessibility service so as to collect input information.

However, one limitation of this is it's unable to collect data within password fields.