>Is it possible to create a network for all my sites?
Yes, generally speaking. Depending on your webhost you may run into certain limitations or issues, but that's the whole idea of WP multi-site: you can run multiple WP websites from a single codebase and database.
>Must all the websites be in the same hosting?
In the end, yes. Let's say you have A.com, B.com, C.com, and D.com all on different hosts. You would create a new hosting plan, let's say on E.com, install WP multi-site, and then migrate all 4 of your other websites into the new WP multi-site installation.
>Should all the websites use the same database?
Yes they will use a single database associated with the WP multi-site installation.