In your themes functions.php file you can check wether or not it get’s installed for the first time on that blog. This can be done by using an option. An option can be set to flag that it’s installing.
This option that signals that an install is immanent can be used in a hook of the init jointcut so to flag for automatic widget registration. Widgets can be registerd with wp_set_sidebars_widgets(). After that’s done, kill the flag.
Keep in mind that switching themes kills the widgets configuration. So this is for first-time use only.
A full working example on how to register widgets on theme activation can be found in the Semiologic Reloaded Theme. It’s available for download, feel free to suit yourself.