I can't seem to find a gun or any way to progress in Cave Story+. I'm currently at the very beginning and I can't tell if this is just glitched or if I am just completely missing where I pick up a gun.
You have to steal the first gun (The Polar Star) from the Gunsmith's House. You'll have to evade a couple of screen's worth of enemies to get there, though. The only tricky part is the first jump over the water, where you'll have to jump before you walk off the end of the shore, or you'll end up unable to get over the barrier.
Here's a Let's Play of the first level, taking you down to the Gunsmith's House: