You are very unlikely to be able to package MDSE with your app, you might be able to though, using something like Wise or Installshield, which gives you a bit more flexibilty and in some cases like Wise provide a scripting lanaguage which allows you even more flexibility in creating install packages though these do come at a price.
If the user had MSDE or sql server installed your database could be installed whilst your app was being installed, this is easliy done using a call to OSQL, with a few details from the user (IE user name, password and location of server).
The other option is to have a folder which contains MSDE, a folder containing your database either as a script that the user runs or as database that the user attach's to and a folder with your installation in and a set of concise instructions, though this is not the prettiest of solutions.
Other than that have you checked out if you can create installation scripts/code in VB
.Net, I know the VB6 install package was customizable to a point.