255 tiles are possible with 1 byte. Up to 65536 tiles are possible with two bytes. If you really are using all those tiles in one layer, then yes, you should use 2-byte layers. You might want to consider using larger tiles that cover more of the graphic, however, so you can use fewer tiles. Or, if most of your tiles are mapped tiles, and you are not using the unmapped values, you can redefine those unmapped values to shrink the number of tiles down to less than 255 (maybe).
The short answer, anyway, is that in your situation, you need two bytes per tile.