The multiply by $2$ is no different than in elementary school when you're taught how to divide by $10$, $100$, $1000$, etc. by moving the decimal place. Let me do this backwards as an example. Say you are told that the wavelength of green light is $0.000\ 000\ 510$ meters--how many nanometers is this? The conversion is $0.000000510 \text{ meters } * \frac{10^9 \text{ nm}}{1 \text{ meter}}$. So you just multiply by $10^9$ to get the nanometers. This can be done by moving the decimal nine places to the right: first move it three spots: $000.000510$, next move it three more places ($6$ total): $000000.510$, and finally move it three more (total of $9$): $000000510 = 510$ nm.
Converting Fractional Numbers
Finding decimal values for base two is essentially the same. Formally think about what you are trying to do. Let's find the base $2$ form of a value $x$ which we know is positive and less than $1$:
$$
x = n_1 \frac{1}{2} + n_2\frac{1}{2^2} + n_3\frac{1}{2^3} + \dots = \sum_1^\infty a_n \frac{1}{2^n}
$$
Finding the base two representation amounts to finding all $a_n$ (most of which will be $0$ if the number is "nice"--which most aren't). If we multiply both sides by $2$ then what do we get?
$$
2x = n_1 + n_2\frac{1}{2^1} + n_3\frac{1}{2^2} + \dots = a_1 + \sum_1^\infty a_{n+1}\frac{1}{2^n}
$$
Since this is base $2$, $a_1$ must be either $0$ or $1$. Which one it is will be obvious once we multiply $x$ by $2$. For example if we want to find $x = 0.3125$:
$$
2*0.3125 = 0.625 = a_1 + \sum_1^\infty a_{n+1}\frac{1}{2^n}
$$
$a_1 = 0$ because there is no whole part--we still get a decimal so now we are trying to solve a different problem:
$$
0.625 = \sum_1^\infty b_n\frac{1}{2^n}
$$
This is the same as the original problem! Now we are trying to find the binary representation of $0.625$ (this will give the $b_n$'s). But we need to keep in mind that the $b_n$'s represent $a_{n+1}$ from the original problem! So we recurse:
$$
2*0.625 = 1.25 = b_1 + \sum_1^\infty b_{n+1}\frac{1}{2^n} \rightarrow b_1 = a_2 = 1 \\
0.25 = \sum_1^\infty b_{n+1}\frac{1}{2^n} = \sum_1^\infty c_{n}\frac{1}{2^n} \\
2*0.25 = 0.5 = c_1 + \sum_1^\infty c_{n+1}\frac{1}{2^n} \rightarrow c_1 = b_2 = a_3 = 0 \\
0.5 = \sum_1^\infty c_{n+1}\frac{1}{2^n} = \sum_1^\infty d_{n}\frac{1}{2^n} \\
2*0.5 = 1 = d_1 + \sum_1^\infty d_{n+1}\frac{1}{2^n} \rightarrow d_1 = c_2 = b_3 = a_4 = 1 \\
0 = \sum_1^\infty d_{n+1}\frac{1}{2^n} \rightarrow d_{n > 1} = c_{n > 2} = b_{n > 3} = a_{n > 4} = 0
$$
So this gives: $0.3125_{10} = 0.0101000\dots_{2}$ or just $0.0101_2$ (which indeed is $0.3125 = \frac{5}{16} = \frac{1}{4} + \frac{1}{16}$).
Converting Integers
Now let's look at converting integers to binary it's essentially the same thing except now you don't have powers of $\frac{1}{2}$, you have powers of $2$:
$$
x = a_0 + a_1*2 + a_2*2^2 + a_3*2^3 + \dots = \sum_0^\infty a_n*2^n = a_0 + \sum_1^\infty a_n*2^n = a_0 + 2*\sum_0^\infty a_{n + 1}*2^n
$$
Hopefully that shows why we should divide by $2$. When we divide by $2$ what we are really doing is writing $x = 2\alpha + \beta$, plug that in:
$$
x = 2\alpha_0 + \beta_0 = a_0 + 2*\sum_0^\infty a_{n + 1}*2^n
$$
Clearly $a_0 = \beta_0$ and $\alpha_0 = \sum_0^\infty a_{n + 1}*2^n$. So again, we recurse:
$$
\alpha_0 = 2\alpha_1 + \beta_1 = a_1 + 2\sum_0^\infty a_{n + 2}*2^n \rightarrow a_1 = \beta_1 \\
\alpha_1 = 2\alpha_2 + \beta_2 = a_2 + 2*\sum_0^\infty a_{n + 3}*2^n \rightarrow a_2 = \beta_2 \\
\dots
$$
So, for instance, we can do $x = 45$:
$$
45 = 2*22 + 1 \rightarrow a_0 = 1\\
22 = 2*11 + 0 \rightarrow a_1 = 0\\
11 = 2*5 + 1 \rightarrow a_2 = 1\\
5 = 2*2 + 1 \rightarrow a_3 = 1\\
2 = 2*1 + 0 \rightarrow a_4 = 0\\
1 = 2*0 + 1 \rightarrow a_5 = 1\\
0 = 2*0 + 0 \rightarrow a_6 = 0 \\
\dots \\
\text{it repeats--these are the zeros to the left of the integer}
$$
So this gives $45_{10} = 0\dots000101101_2$ or just $101101_2$. The way we recursed suggests that we could write:
\begin{align}
45 = & 2*22 + 1 \\
=& 2*\left(2*11 + 0\right) + 1\\
=& 2*\left(2*\left(2*5 + 1\right) + 0\right) + 1\\
=& 2*\left(2*\left(2*\left(2*2 + 1\right) + 1\right) + 0\right) + 1 \\
=& 2*\left(2*\left(2*\left(2*\left(2*1 + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\
=& 2*\left(2*\left(2*\left(2*\left(2*\left(2*0 + 1\right) + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\
=& 2*\left(2*\left(2*\left(2*\left(2*\left(2*\left(2*0 + 0\right) + 1\right) + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\
=& 2*\left(2*\left(2*\left(2*\left(2*\left(2*\left(2*\left(2*0 + 0\right) + 0\right) + 1\right) + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\
=&\dots
\end{align}
The reason that you divide to get the integer value and multiply to get the fractional value is because you are moving the digits towards the one's place: $2^0$. When the digits are to the left of the decimal (integers) you need to divide by $2$ to move them towards $2^0$ and when the digits are to the right of the decimal (fractions) then you need to multiply by $2$ to bring the digits closer to $2^0$.
Another example: base $3$
Let's say we want to find $45_{10}$ in base $3$. It's the same procedure--divide by $3$:
\begin{align}
45 =& 3*15 + 0 \\
=& 3*\left(3*5 + 0\right) + 0 \\
=& 3*\left(3*\left(3*1 + 2\right) + 0\right) + 0 \\
=& 3*\left(3*\left(3*\left(3*0 + 1\right) + 2\right) + 0\right) + 0 \\
=& 3*\left(3*\left(3*\left(3*\left(3*0 + 0\right) + 1\right) + 2\right) + 0\right) + 0 \\
\end{align}
So now that we are starting to get $0$'s, we know that $45_{10} = 0\dots001200_3 = 1200_3 = 1*3^3 + 2*3^2 = 27 + 18 = 45$
I'd say the most efficient mental way to go from decimal to hexadecimal is the division by 16 approach you mention.
123 in hexadecimal? That's 7 remainder 11. Write down the remainder (11), but in hexadecimal, which is B. Since the remaining number is less than 16, you can write that down to the left of the previous number, as well: 7b16!
It's a little longer with numbers of 256 (162), of course, but the process remains the same. Let's try 657:
657 ÷ 16 = 41, renainder 1. Write the remainder: 1
41 ÷ 16 = 2 remainder 9. Write the remainder to the left of the previous number: 91
Since 2 is smaller than 16, we can just write it down to the left of the previous numbers: 291
There you have it - conversion to hex in just 3 steps! Writing the numbers down as you go helps ease the mental strain, and since you have to write the answer down at some point, you might as well do it WHILE you're going through the process.
Best Answer
This is quite a trivial question, since those are just the terms we use for those bases. It's like asking "why are humans people?"; it's just a word we use. Binary means base-2 and decimal means base-10. There's nothing complicated there.
Base-10 and Carrying
Think about how you represent numbers (integers). It's easy for the first $10$, since we just make a new symbol each time: $0,1,2,3,4,5,6,7,8,9$. But, of course, we don't want to make a new symbol for every new number since it'd get very messy and complicated. So for the number after $9$, we start counting in a new place. So, we put a $1$ (shown in blue) in the place on the left, to get $\color{blue}{1}\text{_}$. Then, in the place on the right, we reset our $9$ to $0$ and start counting all over again (shown in red). Hence, after $9$, we get $\color{blue}{1}\color{red}{0},\color{blue}{1}\color{red}{1},\color{blue}{1}\color{red}{2},\ldots$. The $1$ that we put in the left place is called a carry. Of course, when we get to $19$, we change the $1$ on the left to a $2$ and again, reset the $9$ to a $0$. This may seem obvious, but we need to think about exactly what we're doing.
The whole point of doing this is making it simpler and easier to read numbers. With no loss of clarity, we've managed to represent every integer as a sequence of $10$ symbols. This is the system that we almost always use, and is called base-ten or decimal.
To represent bigger numbers in decimal notation, we'd keep putting a new number on the left every time we can't advance our numbers any further. Hence, $9\mapsto10$, and $99\mapsto100$ and $999\mapsto1000$ and so on. Like I mentioned before, we're carrying the $1$ in each case. What's the common feature among $10,100,100\ldots$? Well, they're all powers of $10$. Think about this, since it's important. We started with $10$ symbols (i.e. $0,1,2,3,\ldots$) but whenever we carry a $1$ (to a new position on the left), we do it at a power of $10$. This isn't a coincidence. This happens because we carry the $1$ every time we've maxed out our count in the other columns, which happens at $9$ and $99$ and so on.
This means that when we write the number $1729$, what we actually mean is $$1\times1000\quad+\quad7\times100\quad+\quad2\times10\quad+\quad9\times1$$
This shows us why base-ten is so fundamentally linked with powers of $10$, because the digits of a number tell you how many $1$'s, $10$'s, $100$'s, etc. there are in it.
Base-2
In base $10$, we started with $10$ symbols. But why? Is there a special reason for choosing $10$? It turns out that no, there is no fundamental, mathematical reason to prefer $10$ symbols to a different number (say $8$ or $12$). Notice that the number of symbols is the base. There are cultural, historical and practical arguments for choosing $10$ but these aren't relevant here. In fact, the Native American Yuki People use base $8$, while the Babylonians used base $12$.
Let's say we wanted to use base $2$ for our counting (i.e. only using $2$ symbols). For simplicity, we use the first $2$ symbols we were using before (i.e. $0$ and $1$). If we were using this system, how would we count? We'd start with $0,1,???$ and then what? Well, we'd do the same thing we did before and put a $1$ to the left of our numbers. Hence $\color{red}{0},\color{red}{1}\mapsto\color{blue}{1}\color{red}{0},\color{blue}{1}\color{red}{1}$.
In fact, just like how we max out our base-$10$ count at $9$ or $99$ or $999\ldots$, etc., we max out our base $2$ count at $1_B$ or $11_B$ or $111\ldots_B$ (the subscript B indicates that these numbers are in base-2). To make this clearer, look at how we count in binary:
$$0,1,10,11,100,101,110,111,1000\ldots$$
Every time we get a number only made of ones, we carry over a $1_B$ to the left. For instance, after $111_B$ we get $1000_B$.
But when do we get $1_B$ or $10_B$ or $100\ldots_B$? Looking at these numbers in decimal form should give a clearer indication: $1,2,4,8,16,\dots$. These are the powers of $2$. Since we've only got $2$ different symbols, we max out our count after $2$ numbers or $2\times2$ numbers, or $2\times2\times2\ldots$.
Hence, base-$2$ is fundamentally related to powers of $2$. When we write the base-$2$ number $1011_B$, we really mean:
$$1\times8\quad+\quad0\times4\quad+\quad1\times2\quad+\quad1\times1$$.
Where $1,2,4,8,\ldots$ are the powers of $2$. In other words, $2^0,2^1,2^2,\ldots$
In general, for any system with $n$ symbols, when you write $31415_{\text{(base $n$)}}$, you mean the following, in base-$10$: $$(3\times n^4)+(1\times n^3)+(4\times n^2)+(1\times n^1)+(5\times n^0)$$
Hopefully this clears up why base $10$ has a sum of powers of $10$ but base $2$ has powers of $2$. It's a natural consequence of using any base.
As I wrote earlier, using base $10$ for representing numbers is heavily influenced by history and society. Most often, the numbers you'll deal with in your life will be between $1$ and $200$. For example, how many years old you are, how many cars are on your street or how many eggs you ate this week. Of course, these numbers are unlikely to be massive. So it makes sense to need a base approximately $10$ since small or large bases aren't practical.
For practical purposes, base-$2$ is too cumbersome since it uses so many numbers (the number $100$ is $1100100_B$ in base-$2$) but base $1000$ is completely unfeasible since you'd need $1000$ different symbols. Can you think of $1000$ symbols that look significantly different? I can't.
Hence, we use a base around $8-16$. Some people have used $8$ before, some $12$ and some $16$. It doesn't really matter too much which one you choose. It's handy for the base to have a lot of divisors, since it lets you write simple expressions for fractions (like how $\frac15=0.2$ in base-$10$). Hence $11$ and $13$ aren't used. It's also handy to have the base divisible by $2$ so that $\frac12$ can have a simple expression. So $7,9,15$ aren't typically used. This leaves us with $8,10,12,14$ and $16$. Base $14$ isn't often used since one of its divisors is $7$, and why should we include $7$ as a divisor but not $3$ or $5$? Nevertheless, $8,10,12$ and $16$ have been widely used as bases. This rule doesn't cover every culture since even base $64$ has been used (though it needed a lot of symbols!). Also, as @ Luís Henrique points out, the mesoamerican Maya civilization used an interesting combination of base-$5$ and base-$20$ in their number system.
Other commenters have pointed out the fact that we have $10$ fingers/toes so it's easy to count base-$10$ numbers with your fingers. But this doesn't have a huge amount of bearing (in written math) since you don't often count with your fingers. As @Luís Henrique points out, this may have been much more important in more primitive societies where numbers could be communicated by hand-signs (instead of with written or spoken words), so it may give a historical basis for using base-$10$. On the other hand, computers use binary (base-$2$) since they represent numbers in electronic states (i.e. a lightbulb being on or off). It makes computers a lot simpler and easier to work with (particularly in the design and manufacture of transistors) for them work in binary. Though there have been computers that use base-$3$ (ternary computers), they are less common.
Hopefully this answers your questions.