Você pode utilizar da seguinte maneira (já fiz de acordo com o código que você forneceu, somente fiz as alterações necessárias, teste e nos informe do resultado):
<input type="checkbox" name="categoria[]" <?= $_REQUEST['categoria'] === $row_cat->categoria_slug ? 'checked' : ''?> value="<?= $row_cat->slug ?>" /> <?= $row_cat->titulo ?>
Modificado de acordo com as informações passadas pelo usuário:
<?php
$result_cat=mysql_query('SELECT * FROM colecoes WHERE activo=1');
while($row_cat=mysql_fetch_object($result_cat)) {
$result_cat_atual = mysql_query("SELECT * FROM categorias_estabelecimentos WHERE estabelecimento_id = ID AND categoria_slug = $row_cat->categoria_slug");//Modificar o id
?>
<div style="float: left; margin: 5px 5px 5px 0px;">
<input type="checkbox" <?= mysql_num_rows($result_cat_atual) > 0 ? 'checked' : '' ?> name="categoria[]" value="<?= $row_cat->slug ?>" /> <?= $row_cat->titulo; ?>
</div>
<?php
}
?>