Well, based on your words "...able to hold a lot of weight...", I would say that is has to be as strong as possible.
But how, you say...
Look how triangles are used. Triangles can not be bent or "squashed" like squares can.
http://en.wikipedia.org/wiki/File:Parts_of_a_truss_bridge.svg
Here's a few things to help.
1 - Round toothpicks are stronger than the square/flat ones.
2 - Put two or three toothpicks together for a stronger stringer. Three round toothpicks glued side-by-side in a triangle like this pretty strong:
O
O O
However, do not let any joints be at the same place. Have the toothpicks overlap, then cut them to end at the same place. You can make a long stringer that way.
When I helped my son do his, we had to use only one box and it held something like 20 or 30 pounds. (long ago)
Good luck...