Although you can use hook_install(), it's best to use hook_enable() to check if the vocabulary exists and, if not, create it programatically:
$vocabularies = taxonomy_vocabulary_get_names();
$pos = array_search('my_vocabulary', $vocabularies);
if ($pos !== FALSE) {
// its a keyed array so the $vid is actually $pos
$vid = $pos;
} else {
// arrays are more convenient to initialize
$vocabulary = array(
'name' => t('My Vocabulary'),
'machine_name' => 'my_vocabulary',
'description' => t('My description'),
'hierarchy' => 1,
'module' => 'your_module', // or nothing
'weight' => 1
);
// argument must be an object
$vocabulary = (object) $vocabulary;
taxonomy_vocabulary_save($vocabulary);
// horray, we have a vid now
$vid = $vocabulary->vid;
}
// now that the vocab exists and you know the $vid, create your terms
// ...