The Drupal variable are cached as one string. But upon calling variable_set() on any page requires this variable cache to be refreshed. This leads to a heavy MySQL query, SELECT * FROM variables. Best practice is to only use this call on administrative tasks. Avoid it on any other page.
If you really need to set values on every page, think about Drupal's caching functions, or even create a custom Drupal caching table for your module.
cache_set('my_module_data', 'cache', serialize($my_data));
You can use variable_get() on any page of course.