Let us say the optimization version of the bin packing problem asks you to give a packing using the fewest bins possible and the decision version asks if it is possible to pack the bins into $k$ bins.
How can you reduce the optimization version to the decision version?
If you only have to answer what the fewest bins possible is then it is clear you can use binary search. But if you actually have to give the packing, I can't see how to do it.
If you could solve the decision problem (do these items fit in k bins) you can obviously solve the optimisation problem (what is the minimum number of bins) using binary search. But you actually want to know what to put into each box. That’s easily done doing the decision problem at most n^2 times.
Let’s say you know k boxes are required and sufficient. Sort the item by descending size. Replace the biggest and second biggest item with one item of their combined size and check if the new items fit into k bins. If not, try the largest and third largest item, and so on. After n attempts, you either know two items that are in the same bin in an optimal solution, or you know the largest item is on its own. And you repeat that, each time you find that you can put two items in the same bin by solving at most n decision problems.
This answer will probably be quite annoying...
To be explicit, your bin packing problem is: find a way of assigning items of size $s_1, \dots, s_k$, to the minimum number of bins such that no bin contains items of total size more than $t$.
Consider the following problem, Non-Uniform Bin Packing: the input is a list of bin sizes and item sizes and we want to know if we can put all the items in the bins so no bin is overflowing. This problem is clearly in NP: an assignment of items to bins is of polynomial size with respect to the input, and we can check in polynomial time if none of the bins are overflowing. Since this problem is in NP, it can be reduced to Bin Packing, which is NP-complete. (This is the annoying part: I've not said how to perform this reduction, because I've not managed to figure it out.)
We can use Non-Uniform Bin Packing to solve your problem in the usual way. We build up the solution by asking, for each item in turn, whether that item can go in each bin. First, as you describe, use binary search to find out how many bins we need; call this $d$. Then, suppose we have a partial solution, in which we have placed items $1, \dots, i$ into bins, and the remaining capacities of the bins are $c_1, \dots, c_d$ (our initial partial solution is that $i=0$, i.e., we've placed no items, and the remaining capacities are $t, \dots, t$). Then, just try placing the $(i+1)$st item in each bin in turn until the Non-Uniform Bin Packing algorithm says that there is a solution for items $i+2, \dots, k$ in the remaining bin capacities. That is, we ask in turn if items $i+2, \dots, k$ can be placed in bins with capacities $c_1-s_{i+1}, c_2, \dots, c_d$, then $c_1, c_2-s_{i+1}, c_3, \dots, c_d$, then ... and finally $c_1, \dots, c_{d-1}, c_d-s_{i+1}$. Do this until you've placed each item and you have your assignment.
There is some inconsistency about whether, in the context of complexity analysis, an optimization problem is defined as asking for the optimal solution or the optimal objective function value. For example, Wikipedia's entry on decision problems says:
There are standard techniques for transforming function and optimization problems into decision problems. For example, in the traveling salesman problem, the optimization problem is to produce a tour with minimal weight. The associated decision problem is: for each $N$, to decide whether the graph has any tour with weight less than $N$. By repeatedly answering the decision problem, it is possible to find the minimal weight of a tour.
The second sentence defines the optimization problem as producing the optimal tour, whereas the last sentence implicitly defines it as producing the weight of the optimal tour.
Similarly, the entry on optimization problems says:
For example, if there is a graph $G$ which contains vertices $u$ and $v$, an optimization problem might be "find a path from $u$ to $v$ that uses the fewest edges". This problem might have an answer of, say, 4.
But 4 is not an "answer" to the problem of "find[ing] a path". So, this quote, too, is inconsistent about whether the optimization problem means finding the optimal solution or finding the optimal objective function value.
I am not trying to wade into a debate here about the quality of Wikipedia entries; I'm just trying to make the point that in common usage, there is an inconsistency about the way "optimization problem" is used, and that inconsistency can lead to confusion about the relationship between decision and optimization problems.
Now, back to your original question. If what you are asking is:
How can you reduce the "find the optimal solution" version of the optimization problem to the decision problem?
then I don't know of a way to do this, though @David Richerby gives one in his answer.
If what you are asking is:
How can you reduce the "find the optimal objective function" version of the optimization problem to the decision problem?
then the answer is, using binary search, as you have pointed out.
And if what you are really asking is:
Why does everyone say you can reduce the optimization problem to the decision problem, when it seems impossible?
then my answer is, when people say you can reduce the optimization problem to the decision problem, they mean the "find the optimal objective function" version of the optimization problem, but they are not always sufficiently clear in articulating that.
Now, from a practical perspective, if you are actually going to solve the decision problem, you usually run some algorithm that determines whether the items can be packed into $k$ bins. That algorithm is most likely going to do the packing, so in the course of your binary search, you will find the actual packings.
