So you love Sonic the Hedgehog and always wanted to make your own, but Sega won't return your calls? This is the place. Or rather, that is the place that this is the message board to. Before you ask any questions, you should read this.
BEFORE YOU START
The wiki here contains many guides to Sonic hacking, and is the definitive source of information for doing so. However, you can't charge in without knowing a few things. First, the difference between hex and a split disassembly.
Hex hacking was the first method by which a Sonic ROM was hacked. What this entails is opening up the binary ROM in a Hex Editor to see the various bytes that make up the ROM image. There needs to be some understanding as to what exactly these bytes are before you start changing them, otherwise it's a chaotic process and you won't get a lot done, and everything essentially needs to be the same size, in the same locations as when you started.
A split disassembly is the binary ROM image split into various files, the code and the data. This is the more modern, arguably more powerful way to hack a ROM. Files can be edited separately and put back together.
Of course, you can hack a ROM without either of these two methods, by using utilities designed for hacking the ROM directly (Sort of automating the hex-hacking process), but this is more than a little bit limiting; you'll be able to change palettes, object positions and level layouts but very little else.
Secondly, it's worth stating that the most is known about hacking for Sonic the Hedgehog (1), followed very closely by Sonic 2. Anything else has information in various quantities, but if you're totally new you should stick to 1 or 2.
FIRST, BABY STEPS
You've decided how you're going to hack your game. You need tools!
Hacking with a utility
SonEd (1) is a very easy place to start. You'll need a Sonic 1, 2 or Sonic 3 & Knuckles ROM, and a savestate (Not for Sonic 2) of the level you wish to edit, but you are limited to (As stated above) palettes, layouts and objects. In the case of Sonic 2, you can also edit graphics, pixel by pixel in the editor.
Esrael Sonic Editor (Or ESE) is a little more powerful. Unlike SonEd, for example, it can edit Sonic 1 special stages.
There is an important thing to note, though. With one exception, if you have hacked a ROM directly with one utility, another won't be able to 'read' it properly. The exception is that any program can seemingly read a Sonic 1 ROM hacked with SonEd1*, but not the other way around. You have been warned; this is a very limited way to hack. If you really don't want to learn anything technical, though - this is the place to start.
*; Remember this, for a point I'll make later.
Hex-hacking is definitely not something I could tell you how to do. To me, it's like looking for a needle in a haystack, and replacing the needle with one of a different colour (That absolutely has got to be the same size and weight) without moving a single other straw of hay. Repeat until you've changed everything you wish.
If this didn't put you off, Hex Workshop will be a good ally to assist you in figuring out most of the hacking guides here: on the Sonic Community Hacking Guide (The ones that aren't, say, SonEd2 specific). Because I'm dyslexic, all these tables of numbers and values make me dizzy (Occasionally physically sick). If that doesn't bother you in the slightest, you may wish to take a look.
Incidentally, you may need to hex-hack some things in a split disassembly, depending on how you wish to edit them (For example, it is possible to port some songs from other games into Sonic games).
Split disassembly hacking
Okay, first you NEED SonEd2. This is a program designed specifically to work on the files split from the ROM. I'll tell you how to edit Sonic 1 in this way.
There is a nice guide here by Qjimbo on how to start, but since I am a very simple person, I can tell you in simple language. Disassemblies are found on this page, and any of the ones by Hivebrain will be good to go for; they should include two important things you'll need;
split.bat -- a batch file which can be double-clicked to split your Sonic 1 ROM (Which must be renamed s1.bin) into the various chunks.
build.bat -- this can be double-clicked to put it all together again.
It has to be noted that SonEd2 initially doesn't handle Green Hill Zone very well. A workaround with this is to simply edit your Green Hill Zone layouts in SonEd1 first before splitting. However, to fix it properly something else has to be done. I'll detail this later.
Before you go any further I recommend you play around a little with the tools you've been given. This is not the time to work on your superüberleet hack, but to experiment and make some things work. Try a new layout or two, go on. Make the hardest (Or easiest) level you can. Or, draw some basic level tiles in SonEd2's tile editor. Knock yourself out. Just make sure you read every possible thing that comes with the programs, or even the Sonic Retro wiki before you post here, and you're more likely to get a good answer as to your problem.
In part two, I help out people who want to make sweet music, fix Green Hill Zone with absolutely no technical know-how, and start on their brave journey into ASM.