Yes page layouts must be added just like custom fields must be added. The change set can still deploy without them, but the page layouts will be missing. EDIT: Salesforce will always create a standard page layout if there is a custom object is deployed without a page layout. Each object must have at least one page layout. If you try to delete the only page layout on an object, it will not let you. An error message that says "Error: You must have at least one page layout" will appear. That is why Salesforce auto-created one.
