Use single quotes for the expression you used:
sed 's/\//\\\//g'
In double quotes, `\` has a special meaning, so you have to backslash it:
sed "s/\//\\\\\//g"
But it's cleaner to change the delimiter:
sed 's=/=\\/=g'
sed "s=/=\\\/=g"