You need to use standard locations for your database location when you publish your program: use the Application Data Folder; e.g. Application Data\Program Name\MYdata.accdb.
Look up Virtual Folder Names in MSDN. The Application Data folder is a virtual folder. So as long as you are using virtual folders, they will install in the same place on any machine. And when you make calls to access the database, make sure that you use the appropriate function to find that virtual folder.
The Application Data Folder is the folder recommended by Microsoft to store your application's data. Use the following format: Application Data\Program Name\MyDatabase.accdb
The problem is not your database engine. The problem is writing code that will be universal on a PC using the Windows Operating System. Also you're in a VB6 forum and you are using VB.NET (Visual Studio 2010).
I realize the word publish can be used to describe the installation process; but it has several different meanings in programming. Just use the word install: e.g. I'm having problems installing my program.