Creating a save file/format is not so difficult, essentially what you are doing is saving your memory structure to disk so that you later can read it and recreate the same memory structure. The main issue you need to consider is how to make sure that a world saved with an earlier version can be loaded by a later version.
To that end it is a good idea to save a version at the start of the file so that you can detect the file your loading to be old and use an older version of the loading code.
Another issue is to use a format that is fast to both save and load, seeing as you will continuously be both saving and loading them as the player moves around the world. The best way to ensure this is to do the least amount of work to convert the memory structure to the file structure and vice versa.
So if you have a 3 dimensional array for an area (chunk) of blocks then you want to write your header (with version number) then spit out the data for each block in your array in a specific order (increasing index order in the array is a good bet). Using a table at the end to store a position of a block and then extra data that needs to be loaded means you don't have to check every block in the chunk to see if it has more data stored when loading, you simply load all blocks in one go and then at the end you go over the special blocks and load their extra data.
As for minecraft, the reason they are restricted to 4096 id's is because they split a 16 bit integer into a 12 and a 4 bit number, the first is the block id, the second is the orientation of the block. If you wish you can save your id's as 32 bit numbers (for a total of 4 294 967 296 different blocks), that way you could create a new block every second and you would have to continue that pace for a bit over 136 years before you run out of numbers.
Using integers might speed things up, but there is no reason to look into that unless you start having performance issues.