Step 1: Design your bridge
A triangle spreads out weight and is much more stable than a simple rectangle or square support. Be sure to incorporate lots of triangles into your bridge design. More popsicle sticks doesn't necessarily mean a stronger bridge.
In fact, according to the internet, "If there is a single most important shape in engineering, it is the triangle. Unlike a rectangle, a triangle cannot be deformed without changing the length of one of its sides or breaking one of its joints. In fact, one of the simplest ways to strengthen a rectangle is to add supports that form triangles at the rectangle's corners or across its diagonal length. A single support between two diagonal corners greatly strengthens a rectangle by turning it into two triangles."[link]
My design consists of two main bottom supports, and two across the top, and then a lot of triangles across the sides, the top and bottom, and going from the bottom of one side to the top of the other. Very similar to the one in the diagram.
Draw your design on paper, and estimate the number of sticks you will need.
Be creative with your design!