There are several ways to do this:
Do everything from scratch: This is what theunravelers suggestion (+1) boils down to - build the form yourself, add your own validation and submit handlers and on submit, build two node objects and save them. You'll have full control/flexibility, but it is quite some work and you need to have a good understanding of Drupals inner workings to get it right.
'Overload' one of your content types with the fields needed by the other and tweak the 'overloaded' content types submit (and partially edit/display) logic to create the other content type from the additional fields, while hiding them on the 'overloaded' one on display and edit. You can find an article describing this approach here. This is a considerably easier approach than #1, but I'd consider it to be a bit 'hackish', because of the content type definition vs. display mismatch.
A less 'hackish' variation of #2 would be to set up your content types normally and just manipulate the edit and submit process via
hook_form_alter(). You'd do more or less the same as with approach #2, but instead of 'overloading' one node with the additional fields upfront, you'd just inject them into the edit form directly on
hook_form_alter(either from scratch or by loading the edit form of the other node in the background and copying the relevant field definitions from that). On form submission, you remove those additional fields while using them to build your other node. This requires a bit more work and knowledge than #2, but should be a bit more stable and easier to adjust/maintain than that, as you do not have to deal with a content type definition vs. display mismatch.
Also, you did not specify how you want to deal with editing of existing nodes - I'd suggest adding a nodereference to one of the nodes to keep track of their association. That way, you could also add the logic to edit both nodes from one form, as well as synchronized deletion, if desired.